제출 #900303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900303		12345678	자리 배치 (IOI18_seats)	C++17	0 / 100	170 ms	36176 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;
int N, v[nx], l[nx];

struct segtree
{
    struct node
    {
        int mn, f, lz;
    } d[4*nx];
    node merge(node a, node b)
    {
        if (a.mn==b.mn) a.f+=b.f;
        if (a.mn<=b.mn) return a;
        else return b;
    }
    void pushlz(int l, int r, int i)
    {
        if (l==r) return d[i].mn+=d[i].lz, d[i].lz=0, void();
        d[2*i].lz+=d[i].lz;
        d[2*i+1].lz+=d[i].lz;
        d[i].mn+=d[i].lz;
        d[i].lz=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i].f=1);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i].lz=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
} s;

void updateseats(int idx, int mul)
{
    if (idx==0||idx==N+1) return;
    int c=(v[idx+1]>v[idx])?1:-1;
    c+=(v[idx-1]>v[idx])?1:-1;
    s.update(1, N, 1, v[idx], N, mul*c);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    N=W;
    for (int i=1; i<=N; i++) l[i]=C[i-1]+1;
    for (int i=1; i<=N; i++) v[l[i]]=i;
    v[0]=v[N+1]=1e9;
    s.build(1, N, 1);
    for (int i=1; i<=N; i++) updateseats(l[i], 1);
}

int swap_seats(int a, int b) {
    a++; b++;
    for (int i=-1; i<=1; i++) updateseats(l[a]+i, -1), updateseats(l[b]+i, -1);
    swap(v[l[a]], v[l[b]]);
    swap(l[a], l[b]);
    /*
    cout<<"update \n";
    for (int i=1; i<=N; i++) cout<<l[i]<<' ';
    cout<<'\n';
    for (int i=1; i<=N; i++) cout<<v[i]<<' ';
    cout<<'\n';*/
    for (int i=-1; i<=1; i++) updateseats(l[a]+i, 1), updateseats(l[b]+i, 1);
    return s.d[1].f;
}

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