Submission #348276

#	Time	Username	Problem	Language	Result	Execution time	Memory
348276		beksultan04	Seats (IOI18_seats)	C++14	Compilation error	0 ms	0 KiB

seats

#include"seats.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef EVAL
#else
#include"grader.cpp"
#endif
vector<pair<int,int>>v;
#define pii pair<int,int>
int h,w;
struct node{
    pii tree[4000005];
    int num=1048576;
    void update(int pos,int val){
        pos+=num-1;
        tree[pos]={val,val};
        pos>>=1;
        while(pos){
            tree[pos]={min(tree[pos<<1].first,tree[pos<<1|1].first),max(tree[pos<<1].second,tree[pos<<1|1].second)};
            pos>>=1;
        }
    }
    pii get(int l,int r){
        pii res={2e9,0};
        l+=num-1;r+=num-1;
        while(l<=r){
            if(l&1){
                res={min(res.first,tree[l].first),max(res.second,tree[l].second)};
                l++;
            }
            if(!(r&1)){
                res={min(res.first,tree[r].first),max(res.second,tree[r].second)};
                r--;
            }
            l>>=1;
            r>>=1;
        }
        return res;
    }
    void build(){
        for(int i=0;i<4000005;i++)tree[i]={2e9,0};
    }
}tree1,tree2;
void give_initial_chart(int H,int W,vector<int>x,vector<int>y){
    tree1.build();
    tree2.build();
    h=H,w=W;
    for(int i=0;i<h*w;i++){
        v.push_back({x[i],y[i]});
        tree1.update(i,x[i]);
        tree2.update(i,y[i]);
    }
}
int swap_seats(int a,int b){
    tree1.update(a,v[b].first);
    tree2.update(a,v[b].second);
    tree1.update(b,v[a].first);
    tree2.update(b,v[a].second);
    swap(v[a],v[b]);
    int ans=0;
    for(int i=0;i<h*w;i++){
        auto tmp=tree1.get(0,i);
        int l=tmp.first;
        int r=tmp.second;
        tmp=tree2.get(0,i);
        int u=tmp.first;
        int d=tmp.second;
        if((r-l+1)*(d-u+1)==i+1)ans++;
        else i=(r-l+1)*(d-u+1)-2;
    }
    return ans;
}

Compilation message (stderr)

Compilation timeout while compiling seats