Submission #848276


Source Code Expand

Copy
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <random>
#include <map>
using namespace std;

typedef long long llong;

std::random_device rd;
std::mt19937 gen(rd());
uniform_real_distribution<double> distribution(0.0, 1.0);

const llong inf = (llong)1e18 + 42;

const int N = 100500;

const int MEM = 200 * 1000 * 1000;
char buf[MEM];
char* bufpt = buf;

struct node {
    static node* null;
    int x;
    node *l, *r;
    llong sz = 0;
    node() {
        l = r = this;
        sz = 0;
    }
    inline void* operator new(size_t sz) {
        void* ret = bufpt;
        bufpt += sz;
        return ret;
    }
    node(int _x) {
        sz = 1;
        x = _x;
        l = r = null;
    }
    node(int _x, node* _l, node* _r) {
        x = _x;
        l = _l;
        r = _r;
        assert(this != l && this != r);
        recalc();
    }
    inline void recalc() {
        sz = min(inf, 1 + l->sz + r->sz);
    }
};

#define null node::null

node* null = new node();

node* merge(node* a, node* b) {
    if (a == null)
        return b;
    else if (b == null)
        return a;
    else {
        double p = (a->sz) * 1.0 / (a->sz + b->sz);
        if (distribution(gen) < p)
            return new node(a->x, a->l, merge(a->r, b));
        else
            return new node(b->x, merge(a, b->l), b->r);
    }
}

pair<node*, node*> split(node* n, llong p) {
    assert(0 <= p && p <= n->sz);
    if (n == null)
        return make_pair(null, null);
    else if (n->l->sz >= p) {
        node *a, *b;
        tie(a, b) = split(n->l, p);
        return make_pair(a, new node(n->x, b, n->r));
    } else {
        node *a, *b;
        tie(a, b) = split(n->r, p - n->l->sz - 1);
        return make_pair(new node(n->x, n->l, a), b);
    }
}

inline node* raise(node* n, llong to) {
    node *a, *b;
    tie(a, b) = split(n, 1);

    node *root = b;

    while (root->sz + 1 < to) {
        root = new node(a->x, root, root);
    }

    root = merge(new node(a->x), root);
    return root;
}

node* lsplit(node* n, llong p) {
    assert(0 <= p && p <= n->sz);
    if (n == null)
        return null;
    else if (n->l->sz >= p)
        return lsplit(n->l, p);
    else
        return new node(n->x, n->l, lsplit(n->r, p - n->l->sz - 1));
}

node* build(int l, int r) {
    if (l > r)
        return null;
    else if (l == r)
        return new node(l, null, null);
    else {
        return new node((l + r) / 2, build(l, (l + r) / 2 - 1), build((l + r) / 2 + 1, r));
    }
}

vector<int> L, R, X;
vector<node*> address;

map<node*, int> id;
int get_id(node* n) {
    auto it = id.find(n);
    if (it == id.end()) {
        int nid = id.size();
        id[n] = nid;
        return nid;
    } else {
        return it->second;
    }
}

void DFS(node* n) {
    int mid = get_id(n);
    if (!id.count(n->l))
        DFS(n->l);
    if (!id.count(n->r))
        DFS(n->r);
    if ((int)L.size() <= (int)mid)
        L.resize(mid + 1), R.resize(mid + 1), X.resize(mid + 1);
    L[mid] = get_id(n->l);
    R[mid] = get_id(n->r);
    X[mid] = n->x;
}

vector<vector<int>> E;
vector<int> val;
vector<llong> np;

void DFS2(node* n) {
    if (n == null)
        return;
    int mid = get_id(n);
    val[mid] = n->x;
    if (!id.count(n->l))
        DFS2(n->l);
    if (!id.count(n->r))
        DFS2(n->r);
    if (n->l != null) {
        int idl = id[n->l];
        E[idl].push_back(mid);
    }
    if (n->r != null) {
        int idr = id[n->r];
        E[idr].push_back(mid);
    }
}

llong ans[N];


void DFS3(int x) {
    llong p = (E[x].size() == 0) ? 1 : 0;
    for (int y : E[x]) {
        if (np[y] == -1) {
            DFS3(y);
        }
        p += np[y];
    }
    ans[val[x]] += p;
    np[x] = p;
}

node* rebuild(int v) {
    if (address[v])
        return address[v];
    address[v] = new node();
    address[v]->x = X[v];
    address[v]->l = rebuild(L[v]);
    address[v]->r = rebuild(R[v]);
    address[v]->recalc();
    if (address[v] == address[v]->l)
        null = address[v];
    return address[v];
}

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    node* root = build(0, n - 1);
    for (int i = 0; i < q; i++) {
        llong x;
        scanf("%lld", &x);
        root = raise(root, x);
        root = lsplit(root, x);
        if (bufpt - buf > 0.99 * MEM) {
            fprintf(stderr, "Rebuild!\nbefore = %d\n", (int)(bufpt - buf));
            L.clear();
            R.clear();
            X.clear();
            DFS(root);
            int rid = get_id(root);
            bufpt = buf;
            address.assign(id.size(), 0);
            id.clear();
            root = rebuild(rid);
            fprintf(stderr, "after = %d\n", (int)(bufpt - buf));
        }
    }
    DFS(root);
    fprintf(stderr, "here!\n");
    fprintf(stderr, "%d\n", (int)id.size());
    E.resize(id.size());
    val.resize(id.size());
    np.assign(id.size(), -1);
    id.clear();
    DFS2(root);
    for (int i = 0; i < (int)id.size(); i++) {
        if (np[i] == -1)
            DFS3(i);
    }
    for (int i = 0; i < n; i++)
        printf("%lld\n", ans[i]);
    //while(true);
}

Submission Info

Submission Time
Task E - Sequential operations on Sequence
User Zlobober
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5361 Byte
Status WA
Exec Time 2126 ms
Memory 243160 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:202:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
./Main.cpp:206:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &x);
                          ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
AC × 12
WA × 5
TLE × 18
RE × 3
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt WA 1270 ms 219544 KB
02.txt WA 1348 ms 219696 KB
03.txt WA 1358 ms 219672 KB
04.txt WA 1289 ms 219660 KB
05.txt WA 1351 ms 219768 KB
06.txt TLE 2125 ms 222808 KB
07.txt TLE 2125 ms 223820 KB
08.txt TLE 2125 ms 222924 KB
09.txt TLE 2125 ms 223052 KB
10.txt TLE 2121 ms 222680 KB
11.txt TLE 2121 ms 223452 KB
12.txt TLE 2125 ms 223060 KB
13.txt TLE 2121 ms 222648 KB
14.txt TLE 2121 ms 222936 KB
15.txt TLE 2122 ms 223064 KB
16.txt TLE 2121 ms 222932 KB
17.txt TLE 2122 ms 223056 KB
18.txt TLE 2125 ms 222808 KB
19.txt TLE 2122 ms 223068 KB
20.txt TLE 2125 ms 223436 KB
21.txt TLE 2123 ms 243160 KB
22.txt TLE 2121 ms 215160 KB
23.txt TLE 2126 ms 227848 KB
24.txt RE 897 ms 202272 KB
25.txt RE 859 ms 202400 KB
26.txt RE 646 ms 193920 KB
27.txt AC 327 ms 128128 KB
28.txt AC 529 ms 175744 KB
29.txt AC 490 ms 172600 KB
30.txt AC 423 ms 131948 KB
31.txt AC 4 ms 256 KB
32.txt AC 159 ms 18400 KB
33.txt AC 4 ms 256 KB
34.txt AC 177 ms 19760 KB
35.txt AC 4 ms 256 KB
36.txt AC 4 ms 256 KB
s1.txt AC 4 ms 256 KB
s2.txt AC 4 ms 256 KB