Submission #610724

#	Time	Username	Problem	Language	Result	Execution time	Memory
610724		alirezasamimi100	Seats (IOI18_seats)	C++17	100 / 100	3639 ms	110736 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back
#define F first
#define S second
#define lc v<<1
#define rc v<<1|1

const int N = 1e6 + 10, inf = 1.05e9;

int n,m,lz[N*4],dx[]={0,0,1,1},dy[]={0,1,1,0},s;
pii f[N*4];
vector<int> A[N],r,c;

void build(int v, int l, int r){
    f[v].S=r-l;
    if(r-l==1) return;
    int m=(l+r)>>1;
    build(lc,l,m);
    build(rc,m,r);
}

void shift(int v, int l, int r){
    f[v].F+=lz[v];
    if(r-l>1){
        lz[lc]+=lz[v];
        lz[rc]+=lz[v];
    }
    lz[v]=0;
}

void upd(int v, int l, int r, int tl, int tr, int x){
    shift(v,l,r);
    if(l>=tr || tl>=r || tl>=tr) return;
    if(l>=tl && r<=tr){
        lz[v]=x;
        return shift(v,l,r);
    }
    int m=(l+r)>>1;
    upd(lc,l,m,tl,tr,x);
    upd(rc,m,r,tl,tr,x);
    f[v].F=min(f[lc].F,f[rc].F);
    f[v].S=0;
    if(f[v].F==f[lc].F) f[v].S+=f[lc].S;
    if(f[v].F==f[rc].F) f[v].S+=f[rc].S;
}

void calc(int x, int y, int k){
    vector<int> vec;
    for(int i=0; i<4; i++){
        vec.pb(A[x+dx[i]][y+dy[i]]);
    }
    sort(vec.begin(),vec.end());
    upd(1,0,s,vec[0],vec[1],k);
    upd(1,0,s,vec[2],vec[3],k);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n=H;
    m=W;
    r=R;
    c=C;
    s=n*m;
    build(1,0,s);
    for(int i=0; i<=n+1; i++) A[i].resize(m+2,inf);
    for(int i=0; i<s; i++){
        r[i]++;
        c[i]++;
        A[r[i]][c[i]]=i;
    }
    for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) calc(i,j,1);
}

int swap_seats(int a, int b) {
    for(int i=0; i<4; i++){
        calc(r[a]-dx[i],c[a]-dy[i],-1);
        calc(r[b]-dx[i],c[b]-dy[i],-1);
    }
    swap(A[r[a]][c[a]],A[r[b]][c[b]]);
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    for(int i=0; i<4; i++){
        calc(r[a]-dx[i],c[a]-dy[i],1);
        calc(r[b]-dx[i],c[b]-dy[i],1);
    }
    return f[1].S;
}

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