Submission #808247

#TimeUsernameProblemLanguageResultExecution timeMemory
808247SupersonicSeats (IOI18_seats)C++14
0 / 100
4011 ms75596 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<ll,ll>> g;int h,w;int n; pair<ll,ll> cmi[1000001];pair<ll,ll> cmx[1000001]; int cl[1000001],cr[1000001],cu[1000001],cd[1000001]; struct FenwickTree { vector<int> bit; // binary indexed tree int n; FenwickTree(int n) { this->n = n; bit.assign(n, 0); } FenwickTree(vector<int> const &a) : FenwickTree(a.size()) { for (size_t i = 0; i < a.size(); i++) add(i, a[i]); } void add(int idx, int val) { for (++idx; idx < n; idx += idx & -idx) bit[idx] += val; } void range_add(int l, int r, int val) { add(l, val); add(r + 1, -val); } int point_query(int idx) { int ret = 0; for (++idx; idx > 0; idx -= idx & -idx) ret += bit[idx]; return ret; } }; FenwickTree tf(1000001); void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { h=H;w=W;n=h*w;for(int i=0;i<n;i++){g.push_back({R[i],C[i]});} //tf=FenwickTree(1000001); /*tf.range_add(0,1000,5); tf.range_add(5,1000,5); cerr<<tf.point_query(2)<<' '<<tf.point_query(8)<<endl;*/ //exit(1); } int swap_seats(int a, int b) { swap(g[a],g[b]); pair<ll,ll> mi,mx;mi={1000001,1000001};mx={-1000001,-1000001}; int lm=1000001,um=1000001,rm=-1000001,dm=-1000001; long long t=0; if(a>b)swap(a,b); if(a>0&&b>0){int i=a-1;t=tf.point_query(i);mi=cmi[i];mx=cmx[i];lm=cl[i];rm=cr[i];um=cu[i];dm=cd[i];} int bb=-1; for(int i=a;i<=b;i++){ mi=min(mi,g[i]);mx=max(mx,g[i]); if(g[i].second<lm)lm=g[i].second; if(g[i].second>rm)rm=g[i].second; if(g[i].first<um)um=g[i].first; if(g[i].first>dm)dm=g[i].first; //cerr<<mi.first<<' '<<mi.second<<" | "<<mx.first<<' '<<mx.second; if((mx.first-mi.first+1)*(mx.second-mi.second+1)==i+1&&rm-lm==mx.second-mi.second&&dm-um==mx.first-mi.first){t++;}//cerr<<" ***";}cerr<<endl; cmi[i]=mi;cmx[i]=mx;cl[i]=lm;cr[i]=rm;cu[i]=um;cd[i]=dm; int c=tf.point_query(i); tf.add(i,t-c); if(i==b)bb=t-c; //cerr<<lm<<'-'<<um<<'-'<<rm<<'-'<<dm<<endl; //cerr<<(lm-rm)<<' '<<mx.second-mi.second<<endl; //cerr<<(lm-rm==mx.second-mi.second)<<' '<<(dm-um==mx.first-mi.first)<<endl; } tf.range_add(b+1,n,bb); return t; } /* 2 3 2 0 0 1 0 1 1 0 1 0 2 1 2 0 5 0 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...