Submission #348268

#	Time	Username	Problem	Language	Result	Execution time	Memory
348268		juggernaut	Seats (IOI18_seats)	C++14	5 / 100	4072 ms	60392 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];
    void update(int v,int l,int r,int pos,int val){
        if(l==r){
            tree[v]={val,val};
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)update(v<<1,l,mid,pos,val);
        else update(v<<1|1,mid+1,r,pos,val);
        tree[v]={min(tree[v<<1].first,tree[v<<1|1].first),max(tree[v<<1].second,tree[v<<1|1].second)};
    }
    pii get(int v,int l,int r,int ql,int qr){
        if(qr<l||r<ql)return {2e9,0};
        if(ql<=l&&r<=qr)return tree[v];
        int mid=(l+r)>>1;
        auto to1=get(v<<1,l,mid,ql,qr);
        auto to2=get(v<<1|1,mid+1,r,ql,qr);
        return {min(to1.first,to2.first),max(to1.second,to2.second)};
    }
}tree1,tree2;
int MX=999999;
void give_initial_chart(int H,int W,vector<int>x,vector<int>y){
    h=H,w=W;
    for(int i=0;i<h*w;i++){
        v.push_back({x[i],y[i]});
        tree1.update(1,0,MX,i,x[i]);
        tree2.update(1,0,MX,i,y[i]);
    }
}
int swap_seats(int a,int b){
    tree1.update(1,0,MX,a,v[b].first);
    tree2.update(1,0,MX,a,v[b].second);
    tree1.update(1,0,MX,b,v[a].first);
    tree2.update(1,0,MX,b,v[a].second);
    swap(v[a],v[b]);
    int ans=0;
    for(int i=0;i<h*w;i++){
        auto tmp=tree1.get(1,0,MX,0,i);
        int l=tmp.first;
        int r=tmp.second;
        tmp=tree2.get(1,0,MX,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;
}

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