제출 #1007878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1007878		bachhoangxuan	Seats (IOI18_seats)	C++17	11 / 100	1188 ms	66148 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1001005;

int N,M,K,p[maxn],c[maxn];
int tree[4*maxn],lazy[4*maxn],cnt[4*maxn];

void update(int l,int r,int id,int tl,int tr,int val){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        lazy[id]+=val;
        tree[id]+=val;
        return;
    }
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
    tree[id]=min(tree[id<<1],tree[id<<1|1]);
    cnt[id]=(tree[id]==tree[id<<1])*cnt[id<<1]+(tree[id]==tree[id<<1|1])*cnt[id<<1|1];
    tree[id]+=lazy[id];
}
void build(int l,int r,int id){
    cnt[id]=r-l+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
}

void add(int x,int val){
    vector<int> a={c[x],c[x-1],c[x-M],c[x-M-1]};
    sort(a.begin(),a.end());
    if(a[0]<a[1]) update(0,K-1,1,a[0],a[1]-1,val);
    if(a[2]<a[3]) update(0,K-1,1,a[2],a[3]-1,val);
}

void cal(int x,int val){
    add(x+1,-1);add(x,-1);add(x+M,-1);add(x+M+1,-1);
    c[x]=val;
    add(x+1,1);add(x,1);add(x+M,1);add(x+M+1,1);
}

void give_initial_chart(int _N, int _M, std::vector<int> R, std::vector<int> C) {
    K=_N*_M;N=_N+2;M=_M+2;
    for(int i=0;i<N;i++) for(int j=0;j<M;j++) c[i*M+j]=K;
    for(int i=0;i<K;i++){
        R[i]++;C[i]++;
        c[R[i]*M+C[i]]=i;
        p[i]=R[i]*M+C[i];
    }
    build(0,K-1,1);
    for(int i=1;i<N;i++) for(int j=1;j<M;j++) add(i*M+j,1);
}

int swap_seats(int a, int b) {
    int x=p[a],y=p[b];
    swap(p[a],p[b]);
    cal(x,b);cal(y,a);
    return cnt[1];
}

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