Submission #906206

#	Time	Username	Problem	Language	Result	Execution time	Memory
906206		promitheas	Seats (IOI18_seats)	C++14	0 / 100	184 ms	48304 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;

//subtask 5, H=1

int NUM[MAXHW];
char D[MAXHW];

struct Node {
public:
    int lowest = -1;
    int lowest_count = -1;
    int total_effect = 0;
    Node* left;
    Node* right;
    Node* L() { return left ? left : left = new Node(); }
    Node* R() { return right ? right : right = new Node(); }

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

    void build(int l, int r) {
        if (l == r) {
            lowest = total_effect = D[l];
            lowest_count = 1;
            return;
        }
        int m = (l + r) >> 1;
        L()->build(l, m);
        R()->build(m + 1, r);
        int ll = left->lowest, lr = right->lowest;
        if (ll < lr)
            lowest = ll, lowest_count = left->lowest_count;
        else if (ll > lr)
            lowest = lr, lowest_count = right->lowest_count;
        else
            lowest = ll, lowest_count = left->lowest_count + right->lowest_count;
        total_effect = left->total_effect + right->total_effect;
    }

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

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

    static Node* make_tree(int l, int r) {
        Node* n = new Node();
        n->build(l, r);
        return n;
    }
};

Node* root = nullptr;

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

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) { //R,C is the row and col of seat #i
    assert(h == 1); //R[i]==1,foreach i
    R = r;
    C = c;
    H = h, W = w;
    for (int i = 0; i < w; i++)
        NUM[C[i]] = i;
    if (w == 1) {
        D[0] = 0; return;
    }
    D[0] = NUM[1] > NUM[0] ? 1 : 0;
    for (int i = 1; i < w - 1; i++)
        D[i] = PM_(NUM[i - 1] > NUM[i]) + PM_(NUM[i + 1] > NUM[i]);
    D[w - 1] = NUM[w - 2] > NUM[w - 1] ? 1 : 0;
    root = Node::make_tree(0, w - 1);
}

void update_pos(int pos, std::vector<std::pair<int,int>>& v) {
    if (pos == 0) {
        D[0] = NUM[1] > NUM[0] ? 1 : 0;
        D[1] = PM_(NUM[0] > NUM[1]) + PM_(NUM[2] > NUM[1]);
        v.push_back({ D[0],0 });
        v.push_back({ D[1],1 });
        return;
    }
    else if (pos == W - 1) {
        D[W - 1] = NUM[W - 2] > NUM[W - 1] ? 1 : 0;
        D[W - 2] = PM_(NUM[W-1]>NUM[W-2]) + PM_(NUM[W-3]>NUM[W-2]);
        v.push_back({ D[W - 1],W - 1 });
        v.push_back({ D[W - 2],W - 2 });
        return;
    }
    for (int i = pos - 1; i <= pos + 1; i++) {
        D[i] = PM_(NUM[i - 1] > NUM[i]) + PM_(NUM[i + 1] > NUM[i]);
        v.push_back({ D[i],i });
    }
}

int swap_seats(int a, int b) {
    int x = C[a], y = C[b];
    if (x > y)
        std::swap(x, y);
    std::swap(NUM[x], NUM[y]);
    vector<pair<int, int>> u; //{nv, pos}
    update_pos(x,u);
    update_pos(y,u);
    std::sort(u.begin(), u.end());
    for (int i = u.size() - 1; i >= 0; i--) {
        root->update(0, W - 1, u[i].second, u[i].first);
    }
    return root->count_zeroes();
}

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