oj.uz

Submission #909155

# Submission time Handle Problem Language Result Execution time Memory
909155 2024-01-17T05:49:34 Z anarch_y Regions (IOI09_regions) C++17
40 / 100
 8000 ms 68780 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 = 4000000;
    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 0;
        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 9564 KB Output is correct
2 Correct 3 ms 9560 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 5 ms 9576 KB Output is correct
5 Correct 8 ms 9604 KB Output is correct
6 Correct 15 ms 9668 KB Output is correct
7 Correct 21 ms 9632 KB Output is correct
8 Correct 26 ms 9676 KB Output is correct
9 Correct 43 ms 12192 KB Output is correct
10 Correct 86 ms 12156 KB Output is correct
11 Correct 185 ms 12392 KB Output is correct
12 Correct 250 ms 14936 KB Output is correct
13 Correct 304 ms 14912 KB Output is correct
14 Correct 689 ms 17236 KB Output is correct
15 Correct 1082 ms 22284 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8069 ms 28292 KB Time limit exceeded
2 Execution timed out 8058 ms 27752 KB Time limit exceeded
3 Execution timed out 8093 ms 32132 KB Time limit exceeded
4 Correct 485 ms 17480 KB Output is correct
5 Correct 501 ms 19296 KB Output is correct
6 Correct 3250 ms 22920 KB Output is correct
7 Correct 5188 ms 25896 KB Output is correct
8 Correct 7905 ms 37372 KB Output is correct
9 Execution timed out 8068 ms 46964 KB Time limit exceeded
10 Execution timed out 8090 ms 54712 KB Time limit exceeded
11 Execution timed out 8003 ms 57120 KB Time limit exceeded
12 Execution timed out 8026 ms 53672 KB Time limit exceeded
13 Execution timed out 8028 ms 55060 KB Time limit exceeded
14 Execution timed out 8025 ms 56636 KB Time limit exceeded
15 Execution timed out 8079 ms 60808 KB Time limit exceeded
16 Execution timed out 8079 ms 68780 KB Time limit exceeded
17 Execution timed out 8054 ms 66668 KB Time limit exceeded