Submission #985420

#	Time	Username	Problem	Language	Result	Execution time	Memory
985420		WongYiKai	Seats (IOI18_seats)	C++17	0 / 100	597 ms	121012 KiB

seats

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

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