oj.uz

Submission #469331

# Submission time Handle Problem Language Result Execution time Memory
469331 2021-08-31T13:42:53 Z MohamedFaresNebili Regions (IOI09_regions) C++14
11 / 100
 2963 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;
using db  = double;
using ii  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;

#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

ld dist(ld x, ld y, ld a, ld b)    { return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
ll gcd(ll a , ll b){ return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b){ return (a * b) / gcd(a , b);}
ll fact(ll n) { return n > 1?(n * fact(n-1)):1;}

const ll MOD = 1000*1000*1000+7;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const long long INF = 1e18;
/// const int nx[4] = {0, 0, -1, 1}, ny[4] = {1, -1, 0, 0};
const int nx[8] = {2, 2, 1, -1, -2, -2, 1, -1};
const int ny[8] = {1, -1, 2, 2, -1, 1, -2, -2};

ll n, r, q, home[2*100005], st[524][200005];
vector<ll>adj[100000]; ll ans[1000][1000];
ll in[2*100005], out[2*100005], timer=0;
void update(int v, int l, int r, int ind, int h) {
    if(l==r) { st[h][v]++; return; }
    int mid=(l+r)/2;
    if(ind<=mid) update(v*2, l, mid, ind, h);
    else update(v*2+1, mid+1, r, ind, h);
    st[h][v]=st[h][v*2]+st[h][v*2+1];
}
void dfs(ll v, ll p) {
    in[v]=timer++;
    for(auto u:adj[v]) {
        if(u==p) continue;
        dfs(u, v);
    }
    out[v]=timer-1;
}
ll query(ll v, ll l, ll r, ll lo, ll hi, ll h) {
    if(l>hi||r<lo) return 0;
    if(l>=lo&&r<=hi) return st[h][v];
    return query(v*2, l, (l+r)/2, lo, hi, h)+query(v*2+1, (l+r)/2+1, r, lo, hi, h);
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    cin>>n>>r>>q; cin>>home[1];
    for(int l=2;l<=n;l++) {
        ll a; cin>>a; cin>>home[l]; adj[a].pb(l);
    }
    dfs(1, 0); int s=n;
    while(__builtin_popcount(s)!=1) s++;
    for(int l=1;l<=n;l++) update(1, 1, s, in[l], home[l]);
    for(int l=1;l<=n;l++) {
        for(int i=1;i<=r;i++)
            ans[home[l]][i]+=query(1, 1, s, in[l], out[l], i);
    }
    while(q--) {
        ll r1, r2; cin>>r1>>r2;
        cout<<ans[r1][r2]<<'\n'<<flush;
    }
    return 0;
}

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2632 KB Output isn't correct
2 Correct 2 ms 2760 KB Output is correct
3 Incorrect 4 ms 2888 KB Output isn't correct
4 Incorrect 7 ms 3144 KB Output isn't correct
5 Correct 11 ms 3528 KB Output is correct
6 Correct 54 ms 8800 KB Output is correct
7 Correct 74 ms 8556 KB Output is correct
8 Correct 92 ms 11164 KB Output is correct
9 Correct 486 ms 30940 KB Output is correct
10 Correct 1058 ms 67964 KB Output is correct
11 Correct 1115 ms 66444 KB Output is correct
12 Correct 2963 ms 130716 KB Output is correct
13 Correct 1970 ms 124420 KB Output is correct
14 Correct 1580 ms 98476 KB Output is correct
15 Runtime error 79 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 131076 KB Execution killed with signal 9
2 Runtime error 96 ms 131076 KB Execution killed with signal 9
3 Runtime error 87 ms 131076 KB Execution killed with signal 9
4 Runtime error 50 ms 7112 KB Execution killed with signal 11
5 Runtime error 51 ms 8960 KB Execution killed with signal 11
6 Runtime error 65 ms 8768 KB Execution killed with signal 11
7 Runtime error 63 ms 9964 KB Execution killed with signal 11
8 Runtime error 72 ms 15424 KB Execution killed with signal 11
9 Runtime error 94 ms 18632 KB Execution killed with signal 11
10 Runtime error 106 ms 24640 KB Execution killed with signal 11
11 Runtime error 118 ms 21880 KB Execution killed with signal 11
12 Runtime error 120 ms 22848 KB Execution killed with signal 11
13 Runtime error 113 ms 23232 KB Execution killed with signal 11
14 Runtime error 123 ms 23412 KB Execution killed with signal 11
15 Runtime error 104 ms 27248 KB Execution killed with signal 11
16 Runtime error 109 ms 32944 KB Execution killed with signal 11
17 Runtime error 105 ms 31740 KB Execution killed with signal 11