oj.uz

Submission #67535

# Submission time Handle Problem Language Result Execution time Memory
67535 2018-08-14T18:29:31 Z imeimi2000 Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 23672 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11640 KB Output is correct
2 Correct 12 ms 11640 KB Output is correct
3 Correct 13 ms 11640 KB Output is correct
4 Correct 14 ms 11640 KB Output is correct
5 Execution timed out 15034 ms 11796 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14728 KB Output is correct
2 Correct 49 ms 15028 KB Output is correct
3 Execution timed out 15064 ms 23672 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23672 KB Output is correct
2 Correct 44 ms 23672 KB Output is correct
3 Correct 49 ms 23672 KB Output is correct
4 Correct 50 ms 23672 KB Output is correct
5 Execution timed out 15026 ms 23672 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11640 KB Output is correct
2 Correct 12 ms 11640 KB Output is correct
3 Correct 13 ms 11640 KB Output is correct
4 Correct 14 ms 11640 KB Output is correct
5 Execution timed out 15034 ms 11796 KB Time limit exceeded
6 Halted 0 ms 0 KB -