Submission #348293

#	Time	Username	Problem	Language	Result	Execution time	Memory
348293		juggernaut	Seats (IOI18_seats)	C++14	0 / 100	565 ms	159444 KiB

seats

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

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