Submission #1052561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052561		Ahmed57	Seats (IOI18_seats)	C++17	0 / 100	1318 ms	247924 KiB

seats

#include "bits/stdc++.h"

using namespace std;
vector<int> c,r;
int pos[1001][1001];
int h,w;
int cst[1001][1001];
pair<int,int> seg[4000001];
int lazy[4000001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = {0,1};
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p].first = min(seg[p*2].first,seg[p*2+1].first);
    seg[p].second = (seg[p*2].first==seg[p].first?seg[p*2].second:0)+(seg[p*2+1].first==seg[p].first?seg[p*2+1].second:0);
}
void prop(int p,int l,int r){
    seg[p].first+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,int val){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p] = val;
        prop(p,l,r);
        return ;
    }
    if(r<lq||l>rq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val);
    update(p*2+1,md+1,r,lq,rq,val);
    seg[p].first = min(seg[p*2].first,seg[p*2+1].first);
    seg[p].second = (seg[p*2].first==seg[p].first?seg[p*2].second:0)+(seg[p*2+1].first==seg[p].first?seg[p*2+1].second:0);
}
set<int> cc[1000001];
set<int> rr[1000001];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    h = H;
    w = W;
    for(int i = 0;i<H*W;i++){
        cc[C[i]].insert(i);
        rr[R[i]].insert(i);
        c.push_back(C[i]);
        r.push_back(R[i]);
    }
    for(int i = 0;i<H*W;i++){
        pos[r[i]][c[i]] = i;
    }
    build(1,0,H*W-1);
    for(int i = 0;i<H*W;i++){
        int cost = 2-(c[i]>0&&pos[r[i]][c[i]-1]<pos[r[i]][c[i]])-(c[i]<W-1&&pos[r[i]][c[i]+1]<pos[r[i]][c[i]]);
        cost += -(r[i]>0&&pos[r[i]-1][c[i]]<pos[r[i]][c[i]])-(r[i]<H-1&&pos[r[i]+1][c[i]]<pos[r[i]][c[i]]);
        update(1,0,H*W-1,i,H*W-1,cost);
        cst[r[i]][c[i]] = cost;
    }
    for(int i = 0;i<H;i++){
        update(1,0,H*W-1,(*rr[i].begin()),H*W-1,-1);
    }
    for(int i = 0;i<W;i++){
        update(1,0,H*W-1,(*cc[i].begin()),H*W-1,-1);
    }
}
int swap_seats(int a, int b){
    set<int> rws;rws.insert(r[a]);rws.insert(r[b]);
    for(auto i:rws){
        update(1,0,h*w-1,(*rr[i].begin()),h*w-1,1);
    }
    rr[r[a]].erase(a);
    rr[r[b]].erase(b);
    rr[r[a]].insert(b);
    rr[r[b]].insert(a);
    for(auto i:rws){
        update(1,0,h*w-1,(*rr[i].begin()),h*w-1,-1);
    }
    set<int> cls;cls.insert(c[a]);cls.insert(c[b]);
    for(auto i:cls){
        update(1,0,h*w-1,(*cc[i].begin()),h*w-1,1);
    }
    cc[c[a]].erase(a);
    cc[c[b]].erase(a);
    cc[c[a]].insert(b);
    cc[c[b]].insert(a);
    for(auto i:cls){
        update(1,0,h*w-1,(*cc[i].begin()),h*w-1,-1);
    }
    set<pair<int,int>> s;
    s.insert({r[a],c[a]});
    s.insert({r[b],c[b]});
    if(c[a]>0)s.insert({r[a],c[a]-1});
    if(r[a]>0)s.insert({r[a]-1,c[a]});
    if(c[a]<w-1)s.insert({r[a],c[a]+1});
    if(r[a]<h-1)s.insert({r[a]+1,c[a]});
    if(c[b]>0)s.insert({r[b],c[b]-1});
    if(r[b]>0)s.insert({r[b]-1,c[b]});
    if(c[b]<w-1)s.insert({r[b],c[b]+1});
    if(r[b]<h-1)s.insert({r[b]+1,c[b]});
    for(auto i:s){
        update(1,0,h*w-1,pos[i.first][i.second],h*w-1,-cst[i.first][i.second]);
    }
    swap(c[a],c[b]);
    swap(r[a],r[b]);
    swap(pos[r[a]][c[a]],pos[r[b]][c[b]]);
    for(auto i:s){
        cst[i.first][i.second] = 2-(i.first>0&&pos[i.first-1][i.second]<pos[i.first][i.second])-(i.first<h-1&&pos[i.first+1][i.second]<pos[i.first][i.second]);
        cst[i.first][i.second] += -(i.second>0&&pos[i.first][i.second-1]<pos[i.first][i.second])-(i.second<w-1&&pos[i.first][i.second+1]<pos[i.first][i.second]);
        update(1,0,h*w-1,pos[i.first][i.second],h*w-1,cst[i.first][i.second]);
    }
    return seg[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