oj.uz

Submission #909141

# Submission time Handle Problem Language Result Execution time Memory
909141 2024-01-17T05:46:07 Z anarch_y Regions (IOI09_regions) C++17
35 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

const int MX = 25001;

struct Node{
    int val;
    int l, r;
};
 
struct Pseg{
    static const int LIM = 3000000;
    Node d[LIM];
    int nex = 0;
    vector<int> loc;
 
    int copy(int cur){
        int x = nex++;
        d[x] = d[cur];
        return x;
    }
 
    void push(int x){
        d[x].val = d[d[x].l].val + d[d[x].r].val;
    }
 
    int build(vector<int>& A, int L, int R){
        int cur = nex++;
        if(L == R){
            if(L < sz(A)) d[cur].val = A[L];
            return cur;
        }
        int M = (L+R)/2;
        d[cur].l = build(A, L, M);
        d[cur].r = build(A, M+1, R);
        push(cur);
        return cur;
    }
 
    void build(vector<int>& A){
        loc[0] = build(A, 0, MX-1);
    }
 
    int upd(int cur, int pos, int v, int L, int R){
        if(R < pos or pos < L) return cur;
        int x = copy(cur);
        if(pos <= L and R <= pos){
            d[x].val += v;
            return x;
        }
        int M = (L+R)/2;
        d[x].l = upd(d[x].l, pos, v, L, M);
        d[x].r = upd(d[x].r, pos, v, M+1, R);
        push(x);
        return x;
    }
 
    int upd(int cur, int id, int v){
        return upd(cur, id, v, 0, MX-1);
    }
 
    int query(int cur, int a, int b, int L, int R){  
        if(R < a or b < L) return 0LL;
        if(a <= L and R <= b) return d[cur].val;
        int M = (L+R)/2;
        int s1 = query(d[cur].l, a, b, L, M);
        int s2 = query(d[cur].r, a, b, M+1, R);
        return s1+s2;
    }
 
    int query(int cur, int a, int b){
        return query(cur, a, b, 0, MX-1);
    }
};

Pseg P;

int query(int x, int y, int c){
    if(x == 0) return P.query(P.loc[y], c, c);
    return P.query(P.loc[y], c, c) - P.query(P.loc[x-1], c, c);
}

const int maxn = 200001;
vector<int> adj[maxn];
int sub[maxn], id[maxn], home[maxn];
vector<int> tour;

void dfs(int s, int p){
    sub[s] = 1;
    tour.pb(s);
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        sub[s] += sub[u];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, R, Q; cin >> N >> R >> Q;
    vector<int> reg[R+1];
    int h; cin >> h;
    reg[h].pb(1); home[1] = h;
    for(int i=2; i<=N; i++){
        int p, r; cin >> p >> r;
        adj[i].pb(p); adj[p].pb(i);
        reg[r].pb(i);
        home[i] = r;
    }
    dfs(1, 0);

    vector<int> A(N, 0);
    for(int i=0; i<N; i++){
        id[tour[i]] = i;
        A[i] = home[tour[i]];
    }

    P.loc.resize(maxn);
    vector<int> t(MX, 0);
    t[A[0]] = 1;
    P.build(t);
    for(int i=1; i<N; i++){
        P.loc[i] = P.upd(P.loc[i-1], A[i], 1);
    }

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        int ans = 0;
        for(auto a: reg[r1]){
            ans += query(id[a], id[a]+sub[a]-1, r2);
        }
        cout << ans << "\n";
        cout.flush();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 3 ms 9568 KB Output is correct
3 Correct 5 ms 9564 KB Output is correct
4 Correct 5 ms 9572 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 11 ms 9664 KB Output is correct
7 Correct 21 ms 9648 KB Output is correct
8 Correct 22 ms 9684 KB Output is correct
9 Correct 42 ms 12204 KB Output is correct
10 Correct 100 ms 12152 KB Output is correct
11 Correct 199 ms 12564 KB Output is correct
12 Correct 181 ms 14932 KB Output is correct
13 Correct 424 ms 14912 KB Output is correct
14 Correct 704 ms 17244 KB Output is correct
15 Correct 1121 ms 22288 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8068 ms 28192 KB Time limit exceeded
2 Execution timed out 8038 ms 27972 KB Time limit exceeded
3 Execution timed out 8073 ms 32112 KB Time limit exceeded
4 Correct 468 ms 17480 KB Output is correct
5 Correct 454 ms 19288 KB Output is correct
6 Correct 3136 ms 22916 KB Output is correct
7 Correct 6635 ms 25888 KB Output is correct
8 Execution timed out 8026 ms 37188 KB Time limit exceeded
9 Execution timed out 8007 ms 47068 KB Time limit exceeded
10 Execution timed out 8019 ms 54608 KB Time limit exceeded
11 Runtime error 164 ms 109336 KB Execution killed with signal 11
12 Runtime error 178 ms 106864 KB Execution killed with signal 11
13 Runtime error 202 ms 108724 KB Execution killed with signal 11
14 Runtime error 186 ms 108800 KB Execution killed with signal 11
15 Runtime error 162 ms 117040 KB Execution killed with signal 11
16 Runtime error 2418 ms 131072 KB Execution killed with signal 9
17 Runtime error 166 ms 128668 KB Execution killed with signal 11