oj.uz

답안 #75319

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

typedef pair<int, int> pii;

pii t[4*NMAX];
int lz[4*NMAX];
pii seats[1000555];
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 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 346 ms 31976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

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

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 31976 KB Output is correct
2 Correct 48 ms 31976 KB Output is correct
3 Correct 62 ms 31976 KB Output is correct
4 Correct 78 ms 31976 KB Output is correct
5 Correct 138 ms 31976 KB Output is correct
6 Runtime error 345 ms 32784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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