oj.uz

답안 #75321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75321 2018-09-09T08:54:59 Z mammamia 자리 배치 (IOI18_seats) C++14
33 / 100
 1367 ms 61280 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 4000005;

typedef pair<int, int> pii;

pii t[4*NMAX];
int lz[4*NMAX];
pii seats[4000555];
int tsz, H, W;

void updateAtPosition(int pos);
void deleteAtPosition(int pos);
void addInterval(int l, int r);
void subInterval(int l, int r);

vector<vector<int>> arr;

int ln(int n){
    return 2*n;
}
int rn(int n){
    return 2*n + 1;
}

pii tcombine(pii a, pii b){
    if(a.first < b.first){
        return a;
    } else if(a.first > b.first) {
        return b;
    } else {
        return {a.first, a.second + b.second};
    }
}

void push(int n){
    if(lz[n]){
        t[n].first += lz[n];
        lz[ln(n)] += lz[n];
        lz[rn(n)] += lz[n];
        lz[n] = 0;
    }
}

void build(int n, int l, int r){
    if(l == r){
        t[n] = {0, 1};
        return;
    }
    int pivot = (l+r)>>1;
    build(ln(n), l, pivot);
    build(rn(n), pivot + 1, r);

    t[n] = tcombine(t[ln(n)], t[rn(n)]);
}

void update(int n, int l, int r, int ql, int qr, int add){
    push(n);
    if(ql <= l && r <= qr){
        lz[n] += add;
        push(n);
        return;
    }
    int pivot = (l+r)>>1;
    if(ql <= pivot)
        update(ln(n), l, pivot, ql, qr, add);
    if(qr > pivot)
        update(rn(n), pivot+1, r, ql, qr, add);

    push(ln(n));
    push(rn(n));
    t[n] = tcombine(t[ln(n)], t[rn(n)]);

}

void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
    W = _W;
    H = _H;
    tsz = H*W; // add the right endpoint
    build(1, 1, tsz);
    arr.push_back(vector<int>(W+1, 0));

    for(int i=0; i<W; ++i){
        arr[0][C[i] + 1] = i + 1;
        seats[i] = {1, C[i] + 1};
    }

    for(int i=2; i<=W+1; ++i){
        updateAtPosition(i);
    }
    //cout<<"init: \n";
    //cout<<t[1].first<<" "<<t[1].second<<"\n";

}

int swap_seats(int a, int b) {
    a = seats[a].second;
    b = seats[b].second;
    if(a > b){
        swap(a, b);
    }
    //cout<<"swap "<<a<<" "<<b<<"\n";
    deleteAtPosition(a);
    deleteAtPosition(a+1);
    if(b > a + 1)
        deleteAtPosition(b);
    deleteAtPosition(b+1);

    swap(arr[0][a], arr[0][b]);
    swap(seats[arr[0][a]-1], seats[arr[0][b]-1]);

    updateAtPosition(a);
    updateAtPosition(a+1);
    if(b > a + 1)
        updateAtPosition(b);
    updateAtPosition(b+1);

    return (t[1].first == 1 ? t[1].second : 0);
}


void deleteAtPosition(int pos){
    if(pos > 1) {
        if(pos == W+1){
            subInterval(arr[0][pos-1], tsz);
        } else {
            if (arr[0][pos] > arr[0][pos - 1]) {
                subInterval(arr[0][pos - 1], arr[0][pos] - 1);
            }
        }
    }
}

void updateAtPosition(int pos){
    if(pos > 1) {
        if(pos == W+1){
            addInterval(arr[0][pos-1], tsz);
        } else {
            if (arr[0][pos] > arr[0][pos - 1]) {
                addInterval(arr[0][pos - 1], arr[0][pos] - 1);
            }
        }
    }
}

void addInterval(int l, int r){
    //cout<<"add "<<l<<" "<<r<<"\n";
    update(1, 1, tsz, l, r, +1);
}

void subInterval(int l, int r){
    //cout<<"sub "<<l<<" "<<r<<"\n";
    update(1, 1, tsz, l, r, -1);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

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

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 32700 KB Output is correct
2 Correct 41 ms 32700 KB Output is correct
3 Correct 56 ms 32700 KB Output is correct
4 Correct 81 ms 32700 KB Output is correct
5 Correct 131 ms 32700 KB Output is correct
6 Correct 679 ms 59168 KB Output is correct
7 Correct 784 ms 61244 KB Output is correct
8 Correct 530 ms 61244 KB Output is correct
9 Correct 1367 ms 61280 KB Output is correct
10 Correct 698 ms 61280 KB Output is correct
11 Correct 650 ms 61280 KB Output is correct
12 Correct 823 ms 61280 KB Output is correct

Subtask #6
0 / 30.0

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