제출 #348014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348014		juggernaut	자리 배치 (IOI18_seats)	C++14	17 / 100	4100 ms	73928 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;
bool is[1000005];
int ans=0;
int MX=999999;
void give_initial_chart(int H,int W,vector<int>x,vector<int>y){
    h=H,w=W;
    int l=2e9,r=0,u=2e9,d=0;
    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]);
        l=min(l,v[i].first);
        r=max(r,v[i].first);
        u=min(u,v[i].second);
        d=max(d,v[i].second);
        if((r-l+1)*(d-u+1)==i+1){
            ans++;
            is[i]=1;
        }
    }
}
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]);
    if(a>b)swap(a,b);
    auto tmp=tree1.get(1,0,MX,0,a);
    int l=tmp.first;
    int r=tmp.second;
    tmp=tree2.get(1,0,MX,0,a);
    int u=tmp.first;
    int d=tmp.second;
    for(int i=a;i<=b;i++){
        l=min(l,v[i].first);
        r=max(r,v[i].first);
        u=min(u,v[i].second);
        d=max(d,v[i].second);
        bool nw=0;
        if((r-l+1)*(d-u+1)==i+1)nw=1;
        ans-=is[i];
        ans+=nw;
        is[i]=nw;
    }
    return ans;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2

0 5
0 5
*/

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