oj.uz

Submission #469333

# Submission time Handle Problem Language Result Execution time Memory
469333 2021-08-31T13:44:43 Z MohamedFaresNebili Regions (IOI09_regions) C++14
10 / 100
 2037 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[200005], st[524][200005];
vector<ll>adj[200005]; ll ans[1000][1000];
ll in[200005], out[200005], 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
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5064 KB Output isn't correct
2 Correct 4 ms 5064 KB Output is correct
3 Incorrect 5 ms 5192 KB Output isn't correct
4 Incorrect 9 ms 5448 KB Output isn't correct
5 Correct 14 ms 5832 KB Output is correct
6 Correct 70 ms 11112 KB Output is correct
7 Correct 65 ms 10792 KB Output is correct
8 Correct 109 ms 13384 KB Output is correct
9 Correct 474 ms 33232 KB Output is correct
10 Correct 1168 ms 70184 KB Output is correct
11 Correct 1318 ms 68780 KB Output is correct
12 Runtime error 126 ms 131076 KB Execution killed with signal 9
13 Correct 2037 ms 126848 KB Output is correct
14 Correct 1841 ms 100848 KB Output is correct
15 Runtime error 93 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 131076 KB Execution killed with signal 9
2 Runtime error 101 ms 131076 KB Execution killed with signal 9
3 Runtime error 102 ms 131076 KB Execution killed with signal 9
4 Runtime error 54 ms 11848 KB Execution killed with signal 11
5 Runtime error 59 ms 13716 KB Execution killed with signal 11
6 Runtime error 62 ms 13536 KB Execution killed with signal 11
7 Runtime error 69 ms 14724 KB Execution killed with signal 11
8 Runtime error 76 ms 20164 KB Execution killed with signal 11
9 Runtime error 107 ms 21020 KB Execution killed with signal 11
10 Runtime error 97 ms 26068 KB Execution killed with signal 11
11 Runtime error 129 ms 21880 KB Execution killed with signal 11
12 Runtime error 149 ms 23396 KB Execution killed with signal 11
13 Runtime error 109 ms 23628 KB Execution killed with signal 11
14 Runtime error 132 ms 23424 KB Execution killed with signal 11
15 Runtime error 104 ms 27240 KB Execution killed with signal 11
16 Runtime error 124 ms 32960 KB Execution killed with signal 11
17 Runtime error 108 ms 31704 KB Execution killed with signal 11