Submission #67535

#	Time	Username	Problem	Language	Result	Execution time	Memory
67535		imeimi2000	Collapse (JOI18_collapse)	C++17	0 / 100	15064 ms	23672 KiB

collapse

#include "collapse.h"
#include <algorithm>
#include <functional>
#include <stdlib.h>
#include <time.h>
#include <map>

using namespace std;
typedef pair<int, int> pii;

int n, c, q;

vector<pii> seg[1 << 18];
vector<pii> query[100001];
vector<int> ans;
void insertLine(int i, int s, int e, int x, int y, pii v) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        seg[i].push_back(v);
        return;
    }
    int m = (s + e) / 2;
    insertLine(i << 1, s, m, x, y, v);
    insertLine(i << 1 | 1, m + 1, e, x, y, v);
}

pii par1[100001];
int fen1[100001];
int sz1[100001];
int lz1[100001];
pii par2[100001];
int fen2[100001];
int sz2[100001];
int lz2[100001];

struct operate {
    int * p;
    int t;
    int v;
};
void update(int fen[], int i, int v) {
    while (i <= n) {
        fen[i] += v;
        i += i & -i;
    }
}

int sum(int fen[], int i) {
    int ret = 0;
    while (i) {
        ret += fen[i];
        i -= i & -i;
    }
    return ret;
}

vector<operate> res;
void restore() {
    operate i = res.back();
    res.pop_back();
    if (i.t != 0) {
        update(i.p, i.v, i.t);
    }
    else {
        *i.p = i.v;
    }
}

int findDep(pii par[], int x) {
    if (par[x].first) return findDep(par, par[x].first) + 1;
    return 0;
}

int find(pii par[], int x, int t) {
    if (par[x].second <= t) return find(par, par[x].first, t);
    return x;
}

void saveSz(pii par[], int sz[], int x) {
    while (x) {
        res.push_back({ &sz[x], 0, sz[x] });
        x = par[x].first;
    }
}

void lazySz(pii par[], int sz[], int lz[], int x) {
    int sum = 0;
    while (x) {
        sum += lz[x];
        sz[x] += sum;
        x = par[x].first;
    }
}

void merge(pii par[], int fen[], int sz[], int lz[], int x, int y, int t) {
    int px = find(par, x, t);
    int py = find(par, y, t);
    if (px == py) return;
    sz[px] += lz[px];
    if (par[px].first) lz[par[px].first] += lz[px];
    lz[px] = 0;
    sz[py] += lz[py];
    if (par[py].first) lz[par[py].first] += lz[py];
    lz[py] = 0;
    if (sz[px] > sz[py]) swap(px, py);
    pii nxt = par[px];
    
    res.push_back({ &par[px].first, 0, nxt.first });
    res.push_back({ &par[px].second, 0, nxt.second });
    
    res.push_back({ fen, 1, nxt.second });
    res.push_back({ fen, -1, t });
    
    lz[par[px].first] -= sz[px];
    par[px] = pii(py, t);
    lz[par[px].first] += sz[px];
    update(fen, nxt.second, -1);
    update(fen, t, 1);
    
    if (nxt.first) merge(par, fen, sz, lz, nxt.first, py, nxt.second);
}

int answerQuery(int x) {
    return sum(fen1, x) + sum(fen2, n - x);
}

void dnc(int i, int s, int e) {
    int ps = res.size();
    for (pii p : seg[i]) {
        int x, y;
        tie(x, y) = p;
        ++x; ++y;
        saveSz(par1, sz1, x);
        saveSz(par1, sz1, y);
        saveSz(par2, sz2, x);
        saveSz(par2, sz2, y);
        merge(par1, fen1, sz1, lz1, x, y, y);
        merge(par2, fen2, sz2, lz2, x, y, n - x + 1);
        lazySz(par1, sz1, lz1, x);
        lazySz(par2, sz2, lz2, x);
    }
    if (s == e) {
        for (pii p : query[s]) {
            ans[p.second] = n - answerQuery(p.first);
        }
    }
    else {
        int m = (s + e) / 2;
        dnc(i << 1, s, m);
        dnc(i << 1 | 1, m + 1, e);
    }
    while (ps < res.size()) restore();
}

const int inf = 1e6;
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X,
	vector<int> Y, vector<int> W, vector<int> P) {
    for (int i = 1; i <= 100000; ++i) {
        par1[i] = par2[i] = pii(0, inf);
        sz1[i] = sz2[i] = 1;
    }
    n = N;
    c = T.size();
    q = W.size();
    ans.resize(q);
    
    {
        map<pii, int> mp;
        for (int i = 0; i < c; ++i) {
            if (X[i] > Y[i]) swap(X[i], Y[i]);
            if (T[i]) {
                auto it = mp.find(pii(X[i], Y[i]));
                insertLine(1, 1, c, it->second, i, pii(X[i], Y[i]));
                mp.erase(it);
            }
            else {
                mp[pii(X[i], Y[i])] = i + 1;
            }
        }
        for (auto i : mp) {
            insertLine(1, 1, c, i.second, c, i.first);
        }
    }
    for (int i = 0; i < q; ++i) {
        query[W[i] + 1].emplace_back(P[i] + 1, i);
    }
    dnc(1, 1, c);
    return ans;
}

Compilation message (stderr)

collapse.cpp: In function 'void dnc(int, int, int)':
collapse.cpp:152:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ps < res.size()) restore();
            ~~~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35