Submission #1052665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052665		Ahmed57	Seats (IOI18_seats)	C++17	5 / 100	536 ms	81064 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<pair<int,int>,int> seg[400001];
pair<int,int> lazy[400001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = {{0,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.first+=lazy[p].first;
    seg[p].first.second+=lazy[p].second;
    if(l!=r){
        lazy[p*2].first+=lazy[p].first;
        lazy[p*2].second+=lazy[p].second;
        lazy[p*2+1].first+=lazy[p].first;
        lazy[p*2+1].second+=lazy[p].second;
    }
    lazy[p] = {0,0};
}
void update(int p,int l,int r,int lq,int rq,int val1,int val2){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p] = {val1,val2};
        prop(p,l,r);
        return ;
    }
    if(r<lq||l>rq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val1,val2);
    update(p*2+1,md+1,r,lq,rq,val1,val2);
    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);
}
int cn(int st1,int st2,int x){
    int na = 0;
    for(int i = st1;i<st1+2;i++){
        for(int j = st2;j<st2+2;j++){
            if(i<0||j<0||i>=h||j>=w){
                continue;
            }
            if(pos[i][j]<x)na++;
        }
    }
    return na;
}
int dx[4] = {0,0,1,1};
int dy[4] = {0,1,0,1};
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++){
        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++){
        for(int j = 0;j<4;j++){
            int lol = cn(r[i]-dx[j],c[i]-dy[j],i);
            if(lol==1){
                update(1,0,h*w-1,i,h*w-1,-1,0);
            }if(lol==3){
                update(1,0,h*w-1,i,h*w-1,0,-1);
            }
            lol = cn(r[i]-dx[j],c[i]-dy[j],i+1);
            if(lol==1){
                update(1,0,h*w-1,i,h*w-1,1,0);
            }if(lol==3){
                update(1,0,h*w-1,i,h*w-1,0,1);
            }
        }
    }
}
int swap_seats(int a, int b){
    set<pair<int,int>> s;
    for(int x = -1;x<=1;x++){
        for(int y = -1;y<=1;y++){
            if(r[a]+x>=0&&r[a]+x<h&&c[a]+y>=0&&c[a]+y<w){
                s.insert({r[a]+x,c[a]+y});
            }
            if(r[b]+x>=0&&r[b]+x<h&&c[b]+y>=0&&c[b]+y<w){
                s.insert({r[b]+x,c[b]+y});
            }
        }
    }
    for(auto e:s){
        int i = pos[e.first][e.second];
        for(int j = 0;j<4;j++){
            int lol = cn(r[i]-dx[j],c[i]-dy[j],i);
            if(lol==1){
                update(1,0,h*w-1,i,h*w-1,1,0);
            }if(lol==3){
                update(1,0,h*w-1,i,h*w-1,0,1);
            }
            lol = cn(r[i]-dx[j],c[i]-dy[j],i+1);
            if(lol==1){
                update(1,0,h*w-1,i,h*w-1,-1,0);
            }if(lol==3){
                update(1,0,h*w-1,i,h*w-1,0,-1);
            }
        }
    }
    swap(c[a],c[b]);
    swap(r[a],r[b]);
    swap(pos[r[a]][c[a]],pos[r[b]][c[b]]);
    for(auto e:s){
        int i = pos[e.first][e.second];
        for(int j = 0;j<4;j++){
            int lol = cn(r[i]-dx[j],c[i]-dy[j],i);
            if(lol==1){
                update(1,0,h*w-1,i,h*w-1,-1,0);
            }if(lol==3){
                update(1,0,h*w-1,i,h*w-1,0,-1);
            }
            lol = cn(r[i]-dx[j],c[i]-dy[j],i+1);
            if(lol==1){
                update(1,0,h*w-1,i,h*w-1,1,0);
            }if(lol==3){
                update(1,0,h*w-1,i,h*w-1,0,1);
            }
        }
    }
    return seg[1].second;
}

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