Cod sursa(job #2358270)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 27 februarie 2019 23:00:32
Problema Zota & Chidil Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <iostream>
#include<unordered_map>
#include<vector>
#include<utility>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
unordered_map<int,vector<int>> lin;
unordered_map<int,vector<int>> col;
//map<pair<int,int>,bool> expoz;
void intr(int x,int y){
  if(x==0 && y==0)
    return;
  lin[x].push_back(y);
  col[y].push_back(x);
}
void bagabomb(int x,int y){
  intr(x-2,y);
  intr(x-1,y-1);
  intr(x-1,y);
  intr(x-1,y+1);
  intr(x,y-2);
  intr(x,y-1);
  intr(x,y);
  intr(x,y+1);
  intr(x,y+2);
  intr(x+1,y-1);
  intr(x+1,y);
  intr(x+1,y+1);
  intr(x+2,y);
}
long long sol;
int cautblin(int l,int val){
  int pas=0,p2=1<<20;
  if(!(!lin[l].empty() && lin[l][pas]<=val))
    return 0;
  while(p2){
    if(pas+p2<lin[l].size() && lin[l][pas+p2]<=val)
      pas+=p2;
    p2/=2;
  }
  return pas+1;
}
int cautbcol(int c,int val){
  int pas=0,p2=1<<20;
  if(!(!col[c].empty() && col[c][pas]<=val))
    return 0;
  while(p2){
    if(pas+p2<col[c].size() && col[c][pas+p2]<=val)
      pas+=p2;
    p2/=2;
  }
  return pas+1;
}
void solve(int xst,int yst,int xfin,int yfin,char c){
  if(c=='E'){
    sol+=1LL*cautbcol(yst,xfin)-cautbcol(yst,xst);
    return;
  }
  else if(c=='V'){
    sol+=1LL*cautbcol(yst,xst-1)-cautbcol(yst,xfin-1);
  }
  else if(c=='N'){
    sol+=1LL*cautblin(xst,yfin)-cautblin(xst,yst);
  }
  else
    sol+=1LL*cautblin(xst,yst-1)-cautblin(xst,yfin-1);
}
int main()
{
    FILE*fin,*fout;
    fin=fopen("zc.in","r");
    fout=fopen("zc.out","w");
    int n,m,x,y;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=n;i++){
      fscanf(fin,"%d %d",&x,&y);
      bagabomb(x,y);
    }
    for(auto &itr : lin){
      sort(itr.second.begin(),itr.second.end());
      vector <int> aux;
      aux.clear();
      aux.push_back(itr.second.front());
      for(int i=1;i<itr.second.size();i++){
        if(itr.second[i]!=itr.second[i-1])
          aux.push_back(itr.second[i]);
      }
      itr.second=aux;
     /* fprintf(fout,"linia %d:",itr.first);
      for(int i=0;i<itr.second.size();i++)
        fprintf(fout,"%d ",itr.second[i]);
      fprintf(fout,"\n");*/
    }
   // fprintf(fout,"\n\n");
    for(auto &itr : col){
      sort(itr.second.begin(),itr.second.end());
      vector <int> aux;
      aux.clear();
      aux.push_back(itr.second.front());
      for(int i=1;i<itr.second.size();i++){
        if(itr.second[i]!=itr.second[i-1])
          aux.push_back(itr.second[i]);
      }
      itr.second=aux;
     /* fprintf(fout,"coloana %d:",itr.first);
      for(int i=0;i<itr.second.size();i++)
        fprintf(fout,"%d ",itr.second[i]);
      fprintf(fout,"\n");*/
    }
   // fprintf(fout,"\n\n");
    char c;
    int dist;
    x=0;
    y=0;
    for(int i=1;i<=m;i++){
      fscanf(fin," %c%d",&c,&dist);
      if(c=='E'){
        solve(x,y,x+dist,y,c);
        x+=dist;
      }
      else if(c=='V'){
        solve(x,y,x-dist,y,c);
        x-=dist;
      }
      else if(c=='N'){
        solve(x,y,x,y+dist,c);
        y+=dist;
      }
      else{
        solve(x,y,x,y-dist,c);
        y-=dist;
      }
    }
    fprintf(fout,"%lld",sol);
    return 0;
}