Submission #907467

#	Time	Username	Problem	Language	Result	Execution time	Memory
907467		promitheas	Seats (IOI18_seats)	C++14	0 / 100	183 ms	64084 KiB

seats

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define MAXHW 1000000

#define PM_(b) (b?+1:-1)
int H, W;

vector<int> C;
vector<int> R;

int REAL_POS_OF_NUM[MAXHW];
int NUM_AT_REAL_POS[MAXHW];

int DELTA_REAL_POS[MAXHW];
int DELTA_OF_NUM[MAXHW];

struct Node {
    int total_effect;
    int lowest;
    int lowest_count;

    Node* left, * right;

    void update_self() {
        int a = left->lowest;
        int b = right->lowest + left->total_effect;
        if (a > b) {
            lowest = b;
            lowest_count = right->lowest_count;
        }
        else if (a < b) {
            lowest = a;
            lowest_count = left->lowest_count;
        }
        else {
            lowest = a;
            lowest_count = left->lowest_count + right->lowest_count;
        }
        total_effect = left->total_effect + right->total_effect;
    }

    int count_zeroes() {
        return lowest ? 0 : lowest_count;
    }

    Node(int l, int r) {
        if (l == r) {
            total_effect = lowest = DELTA_OF_NUM[l];
            lowest_count = 1;
            left = right = nullptr;
            return;
        }
        int m = (l + r) >> 1;
        left = new Node(l, m);
        right = new Node(m + 1, r);
        update_self();
    }

    void update(int l, int r, int t, int v) {
        if (l == r) {
            assert(l == t);
            total_effect = lowest = v;
            return;
        }
        int m = (l + r) >> 1;
        if (t > m)
            right->update(m + 1, r, t, v);
        else
            left->update(l, m, t, v);
        update_self();
    }
};

Node* root;

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
    C = c, R = r, H = h, W = w;
    assert(h == 1);
    for (int i = 0; i < W; i++)
        REAL_POS_OF_NUM[i] = C[i], NUM_AT_REAL_POS[C[i]] = i;
    DELTA_REAL_POS[0] = PM_(NUM_AT_REAL_POS[1] > NUM_AT_REAL_POS[0]) + 1;
    for (int i = 1; i < W - 1; i++) {
        DELTA_REAL_POS[i] = PM_(NUM_AT_REAL_POS[i - 1] > NUM_AT_REAL_POS[i]) + PM_(NUM_AT_REAL_POS[i + 1] > NUM_AT_REAL_POS[i]);
    }
    DELTA_REAL_POS[W - 1] = PM_(NUM_AT_REAL_POS[W - 2] > NUM_AT_REAL_POS[W - 1]) + 1;
    for (int realpos = 0; realpos < W; realpos++)
        DELTA_OF_NUM[NUM_AT_REAL_POS[realpos]] = DELTA_REAL_POS[realpos];
    DELTA_OF_NUM[0] = DELTA_REAL_POS[REAL_POS_OF_NUM[0]] = 0;
    root = new Node(0, W - 1);
}

void update_seat(int pos) {
    if (pos == 0) {
        DELTA_REAL_POS[0] = PM_(NUM_AT_REAL_POS[1] > NUM_AT_REAL_POS[0]) + 1;
        DELTA_REAL_POS[1] = PM_(NUM_AT_REAL_POS[1 - 1] > NUM_AT_REAL_POS[1]) + PM_(NUM_AT_REAL_POS[1 + 1] > NUM_AT_REAL_POS[1]);
        DELTA_OF_NUM[NUM_AT_REAL_POS[0]] = DELTA_REAL_POS[0];
        DELTA_OF_NUM[NUM_AT_REAL_POS[1]] = DELTA_REAL_POS[1];
    }
    else if (pos == W - 1) {
        DELTA_REAL_POS[W - 1] = PM_(NUM_AT_REAL_POS[W - 2] > NUM_AT_REAL_POS[W - 1]) + 1;
        DELTA_REAL_POS[W - 2] = PM_(NUM_AT_REAL_POS[W - 2 - 1] > NUM_AT_REAL_POS[W - 1]) + PM_(NUM_AT_REAL_POS[W - 2 + 1] > NUM_AT_REAL_POS[W - 2]);
        DELTA_OF_NUM[NUM_AT_REAL_POS[0]] = DELTA_REAL_POS[0];
        DELTA_OF_NUM[NUM_AT_REAL_POS[1]] = DELTA_REAL_POS[1];
    }
    else
    {
        for (int i = pos-1; i <= pos+1; i++) {
            DELTA_REAL_POS[i] = PM_(NUM_AT_REAL_POS[i - 1] > NUM_AT_REAL_POS[i]) + PM_(NUM_AT_REAL_POS[i + 1] > NUM_AT_REAL_POS[i]);
            DELTA_OF_NUM[NUM_AT_REAL_POS[i]] = DELTA_REAL_POS[i];
        }
    }
}

void update_tree(int num) {
    if (num == 0) {
        root->update(0, W - 1, 0, DELTA_OF_NUM[0]);
        root->update(0, W - 1, 1, DELTA_OF_NUM[1]);
    }
    else if (num == W - 1) {
        root->update(0, W - 1, W-1, DELTA_OF_NUM[W-1]);
        root->update(0, W - 1, W-2, DELTA_OF_NUM[W-2]);
    }
    else {
        for (int n = num - 1; n <= num + 1; n++)
            root->update(0, W - 1, n, DELTA_OF_NUM[n]);
    }
}

int swap_seats(int a, int b) { //not real pos
    int arealpos = REAL_POS_OF_NUM[a];
    int brealpos = REAL_POS_OF_NUM[b];
    REAL_POS_OF_NUM[a] = brealpos;
    NUM_AT_REAL_POS[brealpos] = a;
    REAL_POS_OF_NUM[b] = arealpos;
    NUM_AT_REAL_POS[arealpos] = b;
    update_seat(arealpos);
    update_seat(brealpos);
    DELTA_OF_NUM[0] = DELTA_REAL_POS[REAL_POS_OF_NUM[0]] = 0;
    update_tree(a);
    update_tree(b);
    return root->count_zeroes();
}

/*
int main() {
    give_initial_chart(1, 11, { 0,0,0,0,0,0,0,0,0,0,0 }, { 5,4,7,6,3,8,9,10,1,0,2 });
    printf("%d\n", swap_seats(0,1));
}
*/
//9 8 10 4 1 0 3 2 5 6 7
// 5 4 7 6 3 8 9 10 1 0 2

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