oj.uz

Submission #525987

# Submission time Handle Problem Language Result Execution time Memory
525987 2022-02-13T12:11:16 Z idas Regions (IOI09_regions) C++11
100 / 100
 5630 ms 42072 KB 
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define all(x) (x).begin(), (x).end()
#define le(vec) vec[vec.size()-1]
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=2e5+10, R=25010;
int n, r, q, t, rg[N], tin[N], tout[N], id;
ll pre[510][N], pref[N];
vi ad[N], gr[R], st[R];
set<int> big;
mii c;

void build(int u)
{
    tout[u]=tin[u]=++t;
    for(auto x : ad[u]){
        build(x);
        tout[u]=max(tout[u], tout[x]);
    }
}

int main()
{
    setIO();
    cin >> n >> r >> q;
    cin >> rg[0];
    gr[rg[0]].pb(0);
    FOR(i, 1, n)
    {
        int x; cin >> x;
        x--; cin >> rg[i];
        gr[rg[i]].pb(i);
        ad[x].pb(i);
    }
    build(0);

    int sq=sqrt(n);
    FOR(i, 1, r+1)
    {
        if(sz(gr[i])>sq){
            big.insert(i);
        }
    }
    for(auto x : big) c[x]=++id;

    for(auto x : big){
        FOR(i, 0, n+1) pref[i]=0;
        for(auto i : gr[x]){
            pref[tin[i]]++;
            pref[tout[i]+1]--;
        }
        FOR(i, 1, n+1) pref[i]+=pref[i-1];
        FOR(i, 1, r+1)
        {
            for(auto j : gr[i]){
                pre[c[x]][i]+=pref[tin[j]];
            }
        }
    }

    FOR(i, 1, r+1)
    {
        for(auto x : gr[i]){
            st[i].pb(tin[x]);
        }
        sort(all(st[i]));
    }

    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if(!big.count(r1)){
            ll ans=0;
            for(auto i : gr[r1]){
                int le=-1, ri=sz(st[r2])-1;
                while(le<ri){
                    int m=(le+ri+1)/2;
                    if(st[r2][m]>tout[i]) ri=m-1;
                    else le=m;
                }

                int l0=0, r0=sz(st[r2]);
                while(l0<r0){
                    int m0=(l0+r0)/2;
                    if(st[r2][m0]<tin[i]) l0=m0+1;
                    else r0=m0;
                }

                if(le!=-1&&l0!=sz(st[r2])){
                    ans+=le-l0+1;
                }
            }
            cout << ans << endl;
        }
        else{
            cout << pre[c[r1]][r2] << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 3 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 10 ms 6216 KB Output is correct
6 Correct 18 ms 6216 KB Output is correct
7 Correct 31 ms 6216 KB Output is correct
8 Correct 34 ms 6216 KB Output is correct
9 Correct 45 ms 6728 KB Output is correct
10 Correct 85 ms 6728 KB Output is correct
11 Correct 78 ms 6984 KB Output is correct
12 Correct 138 ms 7496 KB Output is correct
13 Correct 212 ms 7112 KB Output is correct
14 Correct 346 ms 7920 KB Output is correct
15 Correct 285 ms 10568 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1851 ms 11588 KB Output is correct
2 Correct 2232 ms 10304 KB Output is correct
3 Correct 2926 ms 13260 KB Output is correct
4 Correct 244 ms 7880 KB Output is correct
5 Correct 346 ms 9416 KB Output is correct
6 Correct 643 ms 13120 KB Output is correct
7 Correct 1248 ms 14912 KB Output is correct
8 Correct 1114 ms 24548 KB Output is correct
9 Correct 2125 ms 15716 KB Output is correct
10 Correct 3266 ms 42072 KB Output is correct
11 Correct 5630 ms 15292 KB Output is correct
12 Correct 1466 ms 18508 KB Output is correct
13 Correct 2149 ms 18624 KB Output is correct
14 Correct 2361 ms 21956 KB Output is correct
15 Correct 3079 ms 23200 KB Output is correct
16 Correct 3112 ms 28484 KB Output is correct
17 Correct 2717 ms 30684 KB Output is correct