Submission #986707

#	Time	Username	Problem	Language	Result	Execution time	Memory
986707		WongYiKai	Seats (IOI18_seats)	C++14	31 / 100	3095 ms	262144 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll maxn = 1500005;
pair<ll,ll> t[maxn*4];
ll lazy[maxn*4],lock2[maxn*4];



ll h,w,n;
vector<ll> c,r;
map<pair<ll,ll>,ll> pos;

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;
    }
}

void change2(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;
  }
  // cout << smallest << " " << ss-1 << " " << 1*e << "\n";
  update(1,0,n-1,smallest,ss-1,1*e);
  ll high = max(max(a,b),max(c,d));
  if (high==n) return;
  if (fail==1){
    // cout << ss << " " << high-1 << " " << 10000000*e << "\n";
    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);
    // cout << trd << " " << high-1 << " " << 10000000*e << "\n";
  }
  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}];
      change2(a,b,c,d,1);
    }
  }
  // for (int i=0;i<n;i++){
  //   cout << query(1,0,n-1,i,i).first << " ";
  // }
  // cout << "\n";
}

int swap_seats(int a, int b) {
  ll ar = r[a];
  ll ac = c[a];
  ll br = r[b];
  ll bc = c[b];
  set<pair<ll,ll>> removed;
  for (int i=ar-1;i<=ar;i++){
    for (int j=ac-1;j<=ac;j++){
      removed.insert({i,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}];
      change2(a2,b2,c2,d2,-1);
    }
  }
  for (int i=br-1;i<=br;i++){
    for (int j=bc-1;j<=bc;j++){
      if (removed.find({i,j})!=removed.end()) continue;
      ll a2 = pos[{i,j}];
      ll b2 = pos[{i,j+1}];
      ll c2 = pos[{i+1,j}];
      ll d2 = pos[{i+1,j+1}];
      change2(a2,b2,c2,d2,-1);
    }
  }
  removed.clear();
  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++){
      removed.insert({i,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}];
      change2(a2,b2,c2,d2,1);
    }
  }
  for (int i=br-1;i<=br;i++){
    for (int j=bc-1;j<=bc;j++){
      if (removed.find({i,j})!=removed.end()) continue;
      ll a2 = pos[{i,j}];
      ll b2 = pos[{i,j+1}];
      ll c2 = pos[{i+1,j}];
      ll d2 = pos[{i+1,j+1}];
      change2(a2,b2,c2,d2,1);
    }
  }
  // for (int i=0;i<n;i++){
  //   cout << query(1,0,n-1,i,i).first << " ";
  // }
  // cout << "\n";
  // for (int i=1;i<=h;i++){
  //   for (int j=1;j<=w;j++){
  //     cout << pos[{i,j}] << " ";
  //   }
  //   cout << "\n";
  // }
  return query(1,0,n-1,0,n-1).second;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30