Submission #1052519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052519		Ahmed57	Seats (IOI18_seats)	C++17	33 / 100	553 ms	73500 KiB

seats

#include "bits/stdc++.h"

using namespace std;
vector<int> c;
int pos[1000001];
int h,w;
int cst[1000001];
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);
}
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]);
    }
    for(int i = 0;i<H*W;i++){
        pos[c[i]] = i;
    }
    build(1,0,W-1);
    for(int i = 0;i<H*W;i++){
        int cost = 1-(c[i]>0&&pos[c[i]-1]<pos[c[i]])-(c[i]<W-1&&pos[c[i]+1]<pos[c[i]]);
        update(1,0,W-1,i,W-1,cost);
        cst[c[i]] = cost;
    }
}
int swap_seats(int a, int b){
    set<int> s;
    s.insert(c[a]);
    s.insert(c[b]);
    if(c[a]>0)s.insert(c[a]-1);
    if(c[a]<w-1)s.insert(c[a]+1);
    if(c[b]>0)s.insert(c[b]-1);
    if(c[b]<w-1)s.insert(c[b]+1);
    for(auto i:s){
        update(1,0,w-1,pos[i],w-1,-cst[i]);
    }
    swap(c[a],c[b]);
    swap(pos[c[a]],pos[c[b]]);
    for(auto i:s){
        cst[i] = 1-(i>0&&pos[i-1]<pos[i])-(i<w-1&&pos[i+1]<pos[i]);
        update(1,0,w-1,pos[i],w-1,cst[i]);
    }
    return seg[1].second;
}

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