제출 #985420

#제출 시각아이디문제언어결과실행 시간메모리
985420WongYiKai자리 배치 (IOI18_seats)C++17
0 / 100
597 ms121012 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 1000005; pair<ll,ll> t[maxn*4]; ll lazy[maxn*4],lock2[maxn*4]; ll h,w,n; vector<ll> c; ll pos[maxn]; void build(ll a[], ll tl, ll tr, ll v){ if (tl==tr){ t[v].first = a[tl]; t[v].second = 1; } else{ ll tm = (tl+tr)>>1; build(a,tl,tm,v*2); build(a,tm+1,tr,v*2+1); if (t[v*2].first==t[v*2+1].first){ t[v].first = t[v*2].first; t[v].second = t[v*2].second+t[v*2+1].second; } else if (t[v*2].first>t[v*2+1].first){ t[v].first = t[v*2+1].first; t[v].second = t[v*2+1].second; } else{ t[v].first = t[v*2].first; t[v].second = t[v*2].second; } } } void update(ll v, ll tl, ll tr, ll l, ll r, ll x){ // if (tl==0&&tr==n-1){ // cout << "adding " << x << " to " << l << "," << r << "\n"; // } if (lazy[v]!=0){ if (lock2[v]==1){ t[v].first = lazy[v]; t[v].second = tr-tl+1; if (tl!=tr){ lazy[v*2] = lazy[v]; lazy[v*2+1] = lazy[v]; lock2[v*2] = 1; lock2[v*2+1] = 1; } lock2[v] = 0; } else{ t[v].first += lazy[v]; if (tl!=tr){ lazy[v*2] += lazy[v]; lazy[v*2+1] += lazy[v]; } } lazy[v] = 0; } if (tr<l||tl>r) return; if (tl>=l&&tr<=r){ t[v].first += x; lazy[v*2] += x; lazy[v*2+1] += x; return; } ll tm = (tl+tr)>>1; update(v*2,tl,tm,l,r,x); update(v*2+1,tm+1,tr,l,r,x); if (t[v*2].first==t[v*2+1].first){ t[v].first = t[v*2].first; t[v].second = t[v*2].second+t[v*2+1].second; } else if (t[v*2].first>t[v*2+1].first){ t[v].first = t[v*2+1].first; t[v].second = t[v*2+1].second; } else{ t[v].first = t[v*2].first; t[v].second = t[v*2].second; } return; } pair<ll,ll> query(ll v, ll tl, ll tr, ll l, ll r){ if (lazy[v]!=0){ if (lock2[v]==1){ t[v].first = lazy[v]; t[v].second = tr-tl+1; if (tl!=tr){ lazy[v*2] = lazy[v]; lazy[v*2+1] = lazy[v]; lock2[v*2] = 1; lock2[v*2+1] = 1; } lock2[v] = 0; } else{ t[v].first += lazy[v]; if (tl!=tr){ lazy[v*2] += lazy[v]; lazy[v*2+1] += lazy[v]; } } lazy[v] = 0; } if (tr<l||tl>r) return {INT_MAX,0}; if (tl>=l&&tr<=r){ return t[v]; } ll tm = (tl+tr)>>1; pair<ll,ll> t1 = query(v*2,tl,tm,l,r); pair<ll,ll> t2 = query(v*2+1,tm+1,tr,l,r); pair<ll,ll> ans; if (t1.first==t2.first){ ans.first = t1.first; ans.second = t1.second+t2.second; } else if (t1.first>t2.first){ ans.first = t2.first; ans.second = t2.second; } else{ ans.first = t1.first; ans.second = t1.second; } return ans; } void set2(ll v, ll tl, ll tr, ll l, ll r, ll x){ if (lazy[v]!=0){ if (lock2[v]==1){ t[v].first = lazy[v]; t[v].second = tr-tl+1; if (tl!=tr){ lazy[v*2] = lazy[v]; lazy[v*2+1] = lazy[v]; lock2[v*2] = 1; lock2[v*2+1] = 1; } lock2[v] = 0; } else{ t[v].first += lazy[v]; if (tl!=tr){ lazy[v*2] += lazy[v]; lazy[v*2+1] += lazy[v]; } } lazy[v] = 0; } if (tr<l||tl>r) return; if (tl>=l&&tr<=r){ t[v].first = x; t[v].second = tr-tl+1; lazy[v*2] = x; lazy[v*2+1] = x; lock2[v*2] = 1; lock2[v*2+1] = 1; return; } ll tm = (tl+tr)>>1; set2(v*2,tl,tm,l,r,x); set2(v*2+1,tm+1,tr,l,r,x); if (t[v*2].first==t[v*2+1].first){ t[v].first = t[v*2].first; t[v].second = t[v*2].second+t[v*2+1].second; } else if (t[v*2].first>t[v*2+1].first){ t[v].first = t[v*2+1].first; t[v].second = t[v*2+1].second; } else{ t[v].first = t[v*2].first; t[v].second = t[v*2].second; } return; } void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { h=H; w=W; n=h*w; ll a[n]; memset(a,0,sizeof(a)); build(a,0,n-1,1); for (int i=0;i<n;i++){ c.push_back(C[i]); pos[C[i]]=i; } pos[n] = n; set2(1,0,n-1,pos[0],n-1,1); // for (int i=0;i<n;i++){ // cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " "; // } // cout << "\n"; for (int i=0;i<n;i++){ ll a=pos[i],b=pos[i+1]; if (a>b){ ll temp = a; a=b; b=temp; } update(1,0,n-1,a,b-1,1); // for (int i=0;i<n;i++){ // cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " "; // } // cout << "\n"; } // for (int i=0;i<n;i++){ // cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " "; // } // cout << "\n"; } int swap_seats(int a, int b) { ll a2 = c[a]; ll b2 = c[b]; if (a2==0){ update(1,0,n-1,a,n-1,-1); ll temp = pos[1]; if (a>temp) update(1,0,n-1,temp,a-1,-1); else update(1,0,n-1,a,temp-1,-1); } else{ ll temp = pos[a2-1]; if (a>temp) update(1,0,n-1,temp,a-1,-1); else update(1,0,n-1,a,temp-1,-1); temp = pos[a2+1]; if (a>temp) update(1,0,n-1,temp,a-1,-1); else update(1,0,n-1,a,temp-1,-1); } if (b2==0){ update(1,0,n-1,b,n-1,-1); ll temp = pos[1]; if (b>temp) update(1,0,n-1,temp,b-1,-1); else update(1,0,n-1,b,temp-1,-1); } else{ ll temp = pos[b2-1]; if (b>temp) update(1,0,n-1,temp,b-1,-1); else update(1,0,n-1,b,temp-1,-1); temp = pos[b2+1]; if (b>temp) update(1,0,n-1,temp,b-1,-1); else update(1,0,n-1,b,temp-1,-1); } pos[a2] = b; pos[b2] = a; c[a] = b2; c[b] = a2; if (a2==0){ //new ll temp = pos[1]; update(1,0,n-1,b,n-1,1); if (b>temp) update(1,0,n-1,temp,b-1,1); else update(1,0,n-1,b,temp-1,1); } else{ //new ll temp = pos[a2-1]; if (b>temp) update(1,0,n-1,temp,b-1,1); else update(1,0,n-1,b,temp-1,1); temp = pos[a2+1]; if (b>temp) update(1,0,n-1,temp,b-1,1); else update(1,0,n-1,b,temp-1,1); } if (b2==0){ //new ll temp = pos[1]; update(1,0,n-1,a,n-1,1); if (a>temp) update(1,0,n-1,temp,a-1,1); else update(1,0,n-1,a,temp-1,1); } else{ //new ll temp = pos[b2-1]; if (a>temp) update(1,0,n-1,temp,a-1,1); else update(1,0,n-1,a,temp-1,1); temp = pos[b2+1]; if (a>temp) update(1,0,n-1,temp,a-1,1); else update(1,0,n-1,a,temp-1,1); } // for (int i=0;i<n;i++){ // cout << query(1,0,n-1,i,i).first << " " << query(1,0,n-1,i,i).second << " "; // } // cout << "\n"; return query(1,0,n-1,0,n-1).second; }
#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...