Submission #986716

#	Time	Username	Problem	Language	Result	Execution time	Memory
986716		WongYiKai	Seats (IOI18_seats)	C++14	31 / 100	1993 ms	250016 KiB

seats

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

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



ll h,w,n;
vector<ll> c,r;
ll pos[maxn*2];

void build(ll a[], ll tl, ll tr, ll v){
    if (tl==tr){
        t[v].first = 0;
        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){
        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){
        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 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;
}

ll convert(ll r2, ll c2){
  return r2*(w+2)+c2;
}

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[1];
  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[convert(R[i]+1,C[i]+1)]=i;
  }
  for (int i=0;i<=w;i++){
    pos[convert(0,i)] = n;
  }
  for (int i=0;i<=h;i++){
    pos[convert(i,w+1)] = n;
  }
  for (int i=1;i<=w+1;i++){
    pos[convert(h+1,i)] = n;
  }
  for (int i=1;i<=h+1;i++){
    pos[convert(i,0)] = n;
  }
  for (int i=0;i<=h;i++){
    for (int j=0;j<=w;j++){
      ll a = pos[convert(i,j)];
      ll b = pos[convert(i,j+1)];
      ll c = pos[convert(i+1,j)];
      ll d = pos[convert(i+1,j+1)];
      change2(a,b,c,d,1);
    }
  }
  C.clear();
  R.clear();
  // for (int i=0;i<n;i++){
  //   cout << query(1,0,n-1,i,i).first << " ";
  // }
  // cout << "\n";
}


set<pair<ll,ll>> removed;

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++){
      removed.insert({i,j});
      ll a2 = pos[convert(i,j)];
      ll b2 = pos[convert(i,j+1)];
      ll c2 = pos[convert(i+1,j)];
      ll d2 = pos[convert(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[convert(i,j)];
      ll b2 = pos[convert(i,j+1)];
      ll c2 = pos[convert(i+1,j)];
      ll d2 = pos[convert(i+1,j+1)];
      change2(a2,b2,c2,d2,-1);
    }
  }
  removed.clear();
  pos[convert(ar,ac)] = b;
  pos[convert(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[convert(i,j)];
      ll b2 = pos[convert(i,j+1)];
      ll c2 = pos[convert(i+1,j)];
      ll d2 = pos[convert(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[convert(i,j)];
      ll b2 = pos[convert(i,j+1)];
      ll c2 = pos[convert(i+1,j)];
      ll d2 = pos[convert(i+1,j+1)];
      change2(a2,b2,c2,d2,1);
    }
  }
  removed.clear();
  // 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[convert(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