제출 #1023877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023877		Dzadzo	자리 배치 (IOI18_seats)	C++17	100 / 100	2270 ms	204544 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
// #define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector<bool>
#define vvb vector<vb>;
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 1000000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
vp t(4*MAXN+1);
int lazy[4*MAXN+1];
pii merge(pii a,pii b) {
    if (a.F>b.F)return b;
    if (a.F<b.F)return a;
    return {a.F,a.S+b.S};
}
void build(int v,int tl,int tr) {
    if (tl==tr)t[v]={0,1};else {
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        t[v]=merge(t[v*2],t[v*2+1]);
    }
}
void push(int v) {
    t[2*v].F+=lazy[v];
    t[2*v+1].F+=lazy[v];
    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];
    lazy[v]=0;
}
void up(int v,int tl,int tr,int l,int r,int delta) {
    if (l>r)return;
    if (tl==l && tr==r) {
        t[v].F+=delta;
        lazy[v]+=delta;
    }else {
        push(v);
        int tm=(tl+tr)/2;
        up(v*2,tl,tm,l,min(r,tm),delta);
        up(v*2+1,tm+1,tr,max(l,tm+1),r,delta);
        t[v]=merge(t[v*2],t[v*2+1]);
    }
}
vvi arr;
vector <vector <bool>> seen;
int n,H,W;
void add(int x,int y,int t) {
    vi v;
    v.pb(arr[x][y]);
    v.pb(arr[x+1][y]);
    v.pb(arr[x][y+1]);
    v.pb(arr[x+1][y+1]);
    sort(v.begin(),v.end());
    up(1,1,n,v[0],min(n,v[1]-1),t);
    up(1,1,n,v[2],min(n,v[3]-1),t);
}
vi R,C;
void give_initial_chart(int h, int w, vi r, vi c) {
    R=r;
    C=c;
    H=h;
    W=w;
    n=H*W;
    build(1,1,n);
    for (int i=0;i<=H+1;i++) {
        vi cur;
        vb CUR;
        for (int j=0;j<=W+1;j++) {
            cur.pb(0);
            CUR.pb(false);
        }
        seen.pb(CUR);
        arr.pb(cur);
    }

    for (int i=0;i<n;i++)arr[R[i]+1][C[i]+1]=i+1;
    for (int i=0;i<=W+1;i++)arr[0][i]=INF,arr[H+1][i]=INF;
    for (int i=0;i<=H+1;i++)arr[i][0]=INF,arr[i][W+1]=INF;

    for (int i=0;i<=H;i++) {
        for (int j=0;j<=W;j++) {
            add(i,j,1);
        }
    }
    // cout<<t[1].S;
}
int swap_seats(int a,int b) {
    vp cur;
    cur.pb({R[a]+1,C[a]+1});
    cur.pb({R[a],C[a]+1});
    cur.pb({R[a]+1,C[a]});
    cur.pb({R[a],C[a]});
    cur.pb({R[b]+1,C[b]+1});
    cur.pb({R[b]+1,C[b]});
    cur.pb({R[b],C[b]+1});
    cur.pb({R[b],C[b]});

    for (auto &[x,y]:cur){
        if (!seen[x][y])add(x,y,-1);
        seen[x][y]=true;
    }
    for (auto &[x,y]:cur)seen[x][y]=false;

    swap(arr[R[a]+1][C[a]+1],arr[R[b]+1][C[b]+1]);
    swap(R[a],R[b]);
    swap(C[a],C[b]);

    for (auto &[x,y]:cur){
        if (!seen[x][y])add(x,y,1);
        seen[x][y]=true;
    }
    for (auto &[x,y]:cur)seen[x][y]=false;

    return t[1].S;
}
/*signed main(){
    give_initial_chart(1,5,{0, 0, 0, 0, 0},{0, 1, 2, 3, 4});
    cout<<swap_seats(0,1)<<'\n';
    cout<<swap_seats(0,3)<<'\n';
    cout<<swap_seats(4,0)<<'\n';
}*/

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