제출 #986693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986693		WongYiKai	자리 배치 (IOI18_seats)	C++17	0 / 100	3135 ms	186192 KiB

seats

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

const ll maxn = 2000005;
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;
  }
  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}];
      change2(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}];
      change2(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}];
      change2(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}];
      change2(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}];
      change2(a2,b2,c2,d2,-1);
    }
  }
  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