oj.uz

답안 #75994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75994 2018-09-11T18:57:12 Z idLe 자리 배치 (IOI18_seats) C++14
0 / 100
 333 ms 16072 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

#define LL (nod << 1)
#define RR LL | 1
#define fi first
#define se second
const int NMAX = 4000010;
vector<int> r;
pii arb[4*NMAX], seats[NMAX];
int lazy[4*NMAX], H, W, N, ar[NMAX];
void build(int nod, int st, int dr);
pii combine(pii a, pii b);
void updateAtPosition(int pos);
void lazy_update(int nod, int st, int dr, int l , int r, int val);
void propag(int nod);
void deleteAtPosition(int pos);

void give_initial_chart(int HH, int WW, vector<int> R, vector<int> C) {
    H = HH; W = WW;
    if (H != 1) return;
    N = H * W;
    build(1, 1, N);
    for (int i=0; i<N; i++){
        seats[i] = {1, C[i] + 1};
        ar[C[i] + 1] = i + 1;
    }
    for (int i=2; i <= W + 1; i++)
        updateAtPosition(i);
}

int swap_seats(int a, int b){
    a = seats[a].se;
    b = seats[b].se;
    if (a > b) swap(a, b);
    deleteAtPosition(a);
    deleteAtPosition(a+1);
    if (b > a + 1) deleteAtPosition(b);
    deleteAtPosition(b+1);
    swap(ar[a], ar[b]);
    swap(seats[ar[a]-1], seats[ar[b]-1]);
    updateAtPosition(a);
    updateAtPosition(a+1);
    if (b > a + 1) updateAtPosition(b);
    updateAtPosition(b+1);
    return (arb[1].fi == 1 ? arb[1].se : 0);
}

void deleteAtPosition(int pos){
    if (pos < 2) return;
    if (pos == W + 1) lazy_update(1, 1, N, ar[pos-1], N, -1);
    else if (ar[pos] > ar[pos-1]) lazy_update(1, 1, N, ar[pos-1], ar[pos] - 1, -1);
}

pii combine(pii a, pii b){
    if (a.fi < b.fi) return a;
    if (b.fi < a.fi) return b;
    return {a.fi, a.se + b.se};
}

void build(int nod, int st, int dr){
    if (st == dr){
        arb[nod] = {0, 1};
        return;
    }
    int mid = (st + dr) >> 1;
    build(LL, st, mid);
    build(RR, mid + 1, dr);
    arb[nod] = combine(arb[LL], arb[RR]);
}

void propag(int nod){
    if (!lazy[nod]) return;
    arb[nod].fi += lazy[nod];
    if (LL <= 2*N - 1){
        lazy[LL] += lazy[nod];
        lazy[RR] += lazy[nod];
    }
    lazy[nod] = 0;
}

void lazy_update(int nod, int st, int dr, int l, int r, int val){
    propag(nod);
    if (st >= l && dr <= r){
        lazy[nod] += val;
        propag(nod);
        return;
    }
    int mid = (st + dr) >> 1;
    if (l <= mid) lazy_update(LL, st, mid, l, r, val);
    if (r > mid) lazy_update(RR, mid+1, dr, l, r, val);
    propag(LL); propag(RR);
    arb[nod] = combine(arb[LL], arb[RR]);
}

void updateAtPosition(int pos){
    if (pos < 2) return;
    if (pos == W + 1) lazy_update(1, 1, N, ar[pos-1], N, 1);
    else if (ar[pos] > ar[pos-1]) lazy_update(1, 1, N, ar[pos-1], ar[pos]-1, 1);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 333 ms 16072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 16072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 16072 KB Output is correct
2 Incorrect 48 ms 16072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -