Submission #165390

#	Time	Username	Problem	Language	Result	Execution time	Memory
165390		theStaticMind	Plahte (COCI17_plahte)	C++14	160 / 160	569 ms	36640 KiB

plahte

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;
struct Rect{
      int dx,dy,ux,uy,id;
      Rect(int a,int b,int c,int d,int e){
            dx=a,dy=b,ux=c,uy=d,id=e;
      }
};
struct Ball{
      int x,y,color,id;
      Ball(int a,int b,int c,int d){
            x=a,y=b,color=c,id=d;
      }
};
vector<Rect> arr;
vector<Ball> shot;
vector<int> Xl;
map<int,int>ptr;
vector<int>seg;
set<int> data[100000];
vector<int> indeg(100000,0);
vector<int>adj[100000];
vector<int> ans(100000,0);
int S,ind=0;
struct W{
      int w,id;
      W(int a,int b){
            w=a,id=b;
      }
      bool operator<(W& A){
            int x,X;
            if(w)x=arr[id].ux;
            else x=shot[id].x;
            if(A.w)X=arr[A.id].ux;
            else X=shot[A.id].x;
            return x<X||(x==X&&w<A.w);
      }
};
vector<W>X;
bool sort_by_dx(int a,int b){
      return arr[a].dx<arr[b].dx;
}
void swap(map<int,int>& data,int w,int q){
      int e=data[w];
      data.erase(w);
      data[q]=e;
}
int get(int a,int b){
      if(a==-1)return b;
      if(b==-1)return a;
      if(arr[a].uy<arr[b].uy)return b;
      else return a;
}
void build(){
      S=(1<<(int)ceil(log2(seg.size())));
      int l=S-seg.size();
      for(int i=0;i<l;i++)seg.pb(-1);
      reverse(all(seg));
      for(int i=1;i<seg.size();i+=2){
            seg.pb(get(seg[i],seg[i-1]));
      }
      seg.pb(-1);
      reverse(all(seg));
}
void update(int j){
      while(j>0){
            seg[j]=get(seg[j*2],seg[j*2+1]);
            j/=2;
      }
}
void add(int id){
      int j=seg.size()-S+ptr[arr[id].dy];
      seg[j]=id;
      update(j/2);
}
void erase(int id){
      int j=seg.size()-S+ptr[arr[id].dy];
      seg[j]=-1;
      update(j/2);
}
int find(int j,int key){
      while(j*2<seg.size()){
            if(seg[j*2+1]!=-1&&arr[seg[j*2+1]].uy>=key)j=j*2+1;
            else if(seg[j*2]!=-1&&arr[seg[j*2]].uy>=key)j=j*2;
            else return -1;
      }
      if(seg[j]!=-1&&arr[seg[j]].uy>=key)
      return seg[j];
      else return -1;
}
int query(int j,int a,int b,int x,int y,int key){
      if(y<a||b<x)return -1;
      if(a<=x&&y<=b){
            return find(j,key);
      }
      int q=query(j*2+1,a,b,(x+y)/2+1,y,key);
      int w=query(j*2,a,b,x,(x+y)/2,key);
      if(q==-1)return w;
      else return q;
}
void dfs(int x){
      for(int i=0;i<adj[x].size();i++){
            int y=adj[x][i];
            dfs(y);
            if(data[x].size()<data[y].size())swap(data[x],data[y]);
            for(set<int>::iterator itr=data[y].begin();itr!=data[y].end();itr++)data[x].insert(*itr);
            data[y].clear();
      }
      ans[x]=data[x].size();
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,m;
      cin>>n>>m;
      for(int i=0;i<n;i++){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            arr.pb(Rect(a,b,c,d,i));
            Xl.pb(i);
            X.pb(W(1,i));
            ptr[b]=0;
      }
      for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            shot.pb(Ball(a,b,c,i));
            X.pb(W(0,i));
            ptr[b]=0;
      }
      sort(all(Xl),sort_by_dx);
      sort(all(X));
      for(map<int,int>::iterator itr=ptr.begin();itr!=ptr.end();itr++){
            itr->second=ind++;
      }
      seg.resize(ptr.size(),-1);
      build();
      ind=0;
      for(int i=0;i<n;i++){
            int id=Xl[i];
            while(ind<X.size()){
                  int w=X[ind].w,d=X[ind].id;
                  ///erasing part
                  if(w){
                        if(arr[d].ux<arr[id].dx){
                              erase(d);
                        }
                        else break;
                  }
                  ///query part
                  else{
                        if(shot[d].x<arr[id].dx){
                              int q=query(1,0,ptr[shot[d].y],0,S-1,shot[d].y);
                              if(q!=-1){
                                    data[q].insert(shot[d].color);
                              }
                        }
                        else break;
                  }
                  ind++;
            }
            int q=query(1,0,ptr[arr[id].dy],0,S-1,arr[id].uy);
            add(id);
            if(q!=-1){
                  adj[q].pb(id);
                  indeg[id]++;
            }
      }
      while(ind<X.size()){
            int w=X[ind].w,d=X[ind].id;
            if(w){
                  erase(d);
            }
            else{
                  int q=query(1,0,ptr[shot[d].y],0,S-1,shot[d].y);
                  if(q!=-1){
                        data[q].insert(shot[d].color);
                  }
            }
            ind++;
      }
      for(int i=0;i<n;i++){
            if(indeg[i]==0){
                  dfs(i);
            }
      }
      for(int i=0;i<n;i++)cout<<ans[i]<<"\n";
}

Compilation message (stderr)

plahte.cpp: In function 'void build()':
plahte.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=1;i<seg.size();i+=2){
                   ~^~~~~~~~~~~
plahte.cpp: In function 'int find(int, int)':
plahte.cpp:89:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(j*2<seg.size()){
             ~~~^~~~~~~~~~~
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<adj[x].size();i++){
                   ~^~~~~~~~~~~~~~
plahte.cpp: In function 'int32_t main()':
plahte.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(ind<X.size()){
                   ~~~^~~~~~~~~
plahte.cpp:178:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(ind<X.size()){
             ~~~^~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32