Submission #583963

#	Time	Username	Problem	Language	Result	Execution time	Memory
583963		20160161simone	Seats (IOI18_seats)	C++14	17 / 100	4070 ms	94604 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll r[N],c[N],h,w,ans[N],a1[N],a2[N],b1[N],b2[N],vis[N];

ll lowbit(ll x){ return x&(-x); }
void add(ll x,ll v){
    x++;
    for(;x<=h*w;x+=lowbit(x)) ans[x]+=v;
}
ll sum(){
    ll temp=0,x=h*w;
    for(;x;x-=lowbit(x)) temp+=ans[x];
    return temp;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    for(ll i=0;i<H*W;i++) r[i]=R[i],c[i]=C[i];
    h=H,w=W;
    add(0,1),vis[0]=1;
    a1[0]=a2[0]=c[0],b1[0]=b2[0]=r[0];
    for(ll i=1;i<h*w;i++){
        a1[i]=min(a1[i-1],c[i]),a2[i]=max(a2[i-1],c[i]);
        b1[i]=min(b1[i-1],r[i]),b2[i]=max(b2[i-1],r[i]);
        if( (a2[i]-a1[i]+1)*(b2[i]-b1[i]+1)==i+1 ) add(i,1),vis[i]=1;
    }
}


int swap_seats(int a, int b) {
    swap(r[a],r[b]),swap(c[a],c[b]);
    if(a>b) swap(a,b);
    for(ll i=a;i<=b;i++){
        if(i){
            a1[i]=min(a1[i-1],c[i]),a2[i]=max(a2[i-1],c[i]);
            b1[i]=min(b1[i-1],r[i]),b2[i]=max(b2[i-1],r[i]);
        }
        else a1[0]=a2[0]=c[0],b1[0]=b2[0]=r[0];
        if( (a2[i]-a1[i]+1)*(b2[i]-b1[i]+1)==i+1 && vis[i]==0 ) add(i,1),vis[i]=1;
        else if( (a2[i]-a1[i]+1)*(b2[i]-b1[i]+1)!=i+1 && vis[i]==1 ) add(i,-1),vis[i]=0;
    }
    return sum();
}

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