Submission #421108

#	Time	Username	Problem	Language	Result	Execution time	Memory
421108		A_D	자리 배치 (IOI18_seats)	C++14	5 / 100	4040 ms	48176 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+100;
struct node{
    int mnx;
    int mny;
    int mxx;
    int mxy;
};
node INF;
int n;
node seg[4*N];
node com(node a,node b)
{
    node ret;
    ret.mnx=min(a.mnx,b.mnx);
    ret.mny=min(a.mny,b.mny);
    ret.mxx=max(a.mxx,b.mxx);
    ret.mxy=max(a.mxy,b.mxy);
    return ret;
}
void update(int p,int s,int e,int i,int x,int y)
{
    if(s==e){
        seg[p].mnx=x;
        seg[p].mxx=x;
        seg[p].mny=y;
        seg[p].mxy=y;
        return;
    }
    int mid=(s+e)/2;
    if(i<=mid){
        update(p*2,s,mid,i,x,y);
    }
    else{
        update(p*2+1,mid+1,e,i,x,y);
    }
    seg[p]=com(seg[p*2],seg[p*2+1]);
}
void fix(node u)
{
    cout<<u.mnx<<" "<<u.mxx<<endl;
    cout<<u.mny<<" "<<u.mxy<<endl;
}
node get(int p,int s,int e,int a,int b)
{
  //  cout<<"\n";
    //cout<<s<<" "<<e<<endl;
//    fix(seg[p]);
//    cout<<"\n";
    if(a<=s&&e<=b)return seg[p];
    if(s>b||e<a)return INF;
    int mid=(s+e)/2;
    return com(
                get(p*2  ,s    ,mid,a,b),
                get(p*2+1,mid+1,e  ,a,b)
                );

}
void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
    INF.mnx=1e7;
    INF.mny=1e7;
    INF.mxx=-1e7;
    INF.mxy=-1e7;
    n=H*W;
    for(int i=0;i<n;i++){
        update(1,0,n-1,i,R[i],C[i]);
    }
}

int swap_seats(int a, int b){
  //  cout<<"\n";
//    cout<<"\n";
    node aa=get(1,0,n-1,a,a);
    node bb=get(1,0,n-1,b,b);
    update(1,0,n-1,a,bb.mnx,bb.mny);
    update(1,0,n-1,b,aa.mnx,aa.mny);
    int i=0,ret=0;
    while(i<n){
        node u=get(1,0,n-1,0,i);
        int k=(u.mxx-u.mnx+1)*(u.mxy-u.mny+1);
        //fix(u);
        if(k==i+1){
            ret++;
            i++;
        }
        else{
            i=k-1;
        }
    }
    return ret;
}

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