Submission #648602

#	Time	Username	Problem	Language	Result	Execution time	Memory
648602		MohammadAghil	Plahte (COCI17_plahte)	C++17	0 / 160	632 ms	88564 KiB

plahte

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
 typedef long double ld; 
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

int n, seg[maxn], par[maxn], ans[maxn];
set<int> cl[maxn];

void shift(int x){
     if(seg[x]+1){
          seg[x<<1] = seg[x<<1|1] = seg[x];
     }
}

void upd(int l, int r, int k, int x = 1, int lx = 0, int rx = n){
     if(l <= lx && r >= rx){
          seg[x] = k;
          return;
     }
     shift(x);
     int mid = (lx + rx)>>1;
     if(l < mid) upd(l, r, k, x<<1, lx, mid);
     if(mid < r) upd(l, r, k, x<<1|1, mid, rx);
     seg[x] = seg[x<<1] == seg[x<<1|1]? seg[x<<1]: -1;
}
int get(int i, int x = 1, int lx = 0, int rx = n){
     if(seg[x] + 1) return seg[x];
     int mid = (lx + rx)>>1;
     if(i < mid) return get(i, x<<1, lx, mid);
     return get(i, x<<1|1, mid, rx);
}

int main(){ IOS();
     int n, m; cin >> n >> m;
     vector<pair<pp, pp>> rec;
     vector<pair<pp, int>> pnt;
     map<int, int> cmpX, cmpY;
     rep(i,0,n){
          int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
          rec.pb({{x1, y1}, {x2, y2}});
          cmpX[x1] = cmpX[x2] = cmpY[y1] = cmpY[y2] = 0; 
     }
     rep(i,0,m){
          int x, y, k; cin >> x >> y >> k;
          cmpX[x] = cmpY[y] = 0;
          pnt.pb({{x, y}, k});
     }
     int id = 0;
     for(auto&c: cmpX) c.ss = id++;
     id = 0;
     for(auto&c: cmpY) c.ss = id++;
     ::n = id;

     rep(i,0,n) rec[i].ff.ff = cmpX[rec[i].ff.ff], rec[i].ff.ss = cmpY[rec[i].ff.ss],
          rec[i].ss.ff = cmpX[rec[i].ss.ff], rec[i].ss.ss = cmpY[rec[i].ss.ss];
     rep(i,0,m) pnt[i].ff.ff = cmpX[pnt[i].ff.ff], pnt[i].ff.ss = cmpY[pnt[i].ff.ss];

     struct Event{
          int l, r, id;
          bool is_add;
     };

     vector<vector<Event>> st(sz(cmpX)+1);
     rep(i,0,n){
          st[rec[i].ff.ff].pb({rec[i].ff.ss, rec[i].ss.ss, i+1, true});
          st[rec[i].ss.ff+1].pb({rec[i].ff.ss, rec[i].ss.ss, i+1, false});
     }
     rep(i,0,m){
          auto[x, y] = pnt[i].ff;
          st[x].pb({y, pnt[i].ss, -1, false});
     }

     rep(i,0,::n+1){
          for(auto[l, r, id, is]: st[i]){
               // er(i, l, r, id, is);
               if(id > 0){
                    if(is){
                         par[id] = get(l);
                         upd(l, r+1, id);
                         // er(par[id]);
                    }
                    else{
                         upd(l, r+1, par[id]);
                         ans[id] = sz(cl[id]);
                         if(sz(cl[id]) > sz(cl[par[id]])) cl[id].swap(cl[par[id]]);
                         for(int c: cl[id]) cl[par[id]].insert(c);
                         cl[id].clear();
                    }
               }else{
                    cl[get(l)].insert(r);
                    // er(get(l));
               }
          } 
     }

     rep(i,1,n+1) cout << ans[i] << '\n';
}

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