| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 986691 | WongYiKai | Seats (IOI18_seats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,r;
ll pos[maxn][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 change(ll a, ll b, ll c, ll d, ll e){
ll smallest = min(min(a,b),min(c,d));
ll ss;
ll fail=0;
if (smallest==a){
ss = min(b,min(c,d));
if (ss==d) fail=1;
}
else if (smallest==b) {
ss = min(a,min(c,d));
if (ss==c) fail=1;
}
else if (smallest==c) {
ss = min(min(a,b),d);
if (ss==b) fail=1;
}
else {
ss = min(min(a,b),c);
if (ss==a) fail=1;
}
update(1,0,n-1,smallest,ss-1,1*e);
ll high = max(max(a,b),max(c,d));
if (fail==1){
update(1,0,n-1,ss,high-1,10000000*e);
}
ll trd;
if (a!=smallest&&a!=ss&&a!=high) trd = a;
else if (b!=smallest&&b!=ss&&b!=high) trd = b;
else if (c!=smallest&&c!=ss&&c!=high) trd = c;
else trd = d;
if (fail==0) update(1,0,n-1,trd,high-1,10000000*e);
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+2];
memset(a,0,sizeof(a));
build(a,0,n-1,1);
for (int i=0;i<n;i++){
c.push_back(C[i]+1);
r.push_back(R[i]+1);
pos[R[i]+1][C[i]+1]=i;
}
for (int i=0;i<=w;i++){
pos[0][i] = n;
}
for (int i=0;i<=h;i++){
pos[i][w+1] = n;
}
for (int i=1;i<=w+1;i++){
pos[h+1][i] = n;
}
for (int i=1;i<=h+1;i++){
pos[i][0] = n;
}
for (int i=0;i<=h;i++){
for (int j=0;j<=w;j++){
ll a = pos[i][j];
ll b = pos[i][j+1];
ll c = pos[i+1][j];
ll d = pos[i+1][j+1];
change(a,b,c,d,1);
}
}
}
int swap_seats(int a, int b) {
ll ar = r[a];
ll ac = c[a];
ll br = r[b];
ll bc = c[b];
for (int i=ar-1;i<=ar;i++){
for (int j=ac-1;j<=ac;j++){
ll a2 = pos[i][j];
ll b2 = pos[i][j+1];
ll c2 = pos[i+1][j];
ll d2 = pos[i+1][j+1];
change(a2,b2,c2,d2,-1);
}
}
for (int i=br-1;i<=br;i++){
for (int j=bc-1;j<=bc;j++){
ll a2 = pos[i][j];
ll b2 = pos[i][j+1];
ll c2 = pos[i+1][j];
ll d2 = pos[i+1][j+1];
change(a2,b2,c2,d2,-1);
}
}
pos[ar][ac] = b;
pos[br][bc] = a;
c[b] = ac;
r[b] = ar;
c[a] = bc;
r[a] = br;
for (int i=ar-1;i<=ar;i++){
for (int j=ac-1;j<=ac;j++){
ll a2 = pos[i][j];
ll b2 = pos[i][j+1];
ll c2 = pos[i+1][j];
ll d2 = pos[i+1][j+1];
change(a2,b2,c2,d2,-1);
}
}
for (int i=br-1;i<=br;i++){
for (int j=bc-1;j<=bc;j++){
ll a2 = pos[i][j];
ll b2 = pos[i][j+1];
ll c2 = pos[i+1][j];
ll d2 = pos[i+1][j+1];
change(a2,b2,c2,d2,-1);
}
}
return query(1,0,n-1,0,n-1).second;
}