oj.uz

Submission #1062387

# Submission time Handle Problem Language Result Execution time Memory
1062387 2024-08-17T05:43:26 Z LilPluton Fountain (eJOI20_fountain) C++14
100 / 100
 217 ms 44748 KB 
#include <bits/stdc++.h>
/// author: LilPluton auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
using namespace std;
#define ll long long
#define ld long double
#define ar array
#define int ll
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define endll   '\n'
#define lb(a, x)    lower_bound(all(a), x) - a.begin();

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
     
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
struct BIT
{
    long long n;
    vector<long long> ft;
    BIT(long long N)
    {
        n = N;
        ft.assign(n + 5, 0);
    }
    void upd(long long pos, long long val)
    {
        while(pos <= n)
        {
            ft[pos] += val;
            pos += (pos & (-pos));
        }
        
    }
    long long sum(long long l, long long r)
    {
        if(l != 1)  return sum(1, r) - sum(1, l - 1);
        long long res = 0;
        while(r >= 1)
        {
            res +=  ft[r];
            r += (r | (-r));
        }
        return res;
    }
};
struct DSU
{
    vector<int>par, size;
    int n;
    DSU(int N)
    {
        n = N + 5;
        par.resize(n + 1, 0);
        size.assign(n + 1, 1);
        for(int i = 0; i <= n; ++i)
            par[i] = i;
    }
    int _find(int v)
    {
        if(par[v] == v)
            return v;
        return par[v] = _find(par[v]);
    }
    bool unite(int a, int b)
    {
        a = _find(a);
        b = _find(b);
        if(a != b)
        {
            if(size[a] < size[b])
                swap(a, b);
            size[a] += size[b];
            par[b] = a;
            return 1;
        }
        return 0;
    }
};
const long long inf = 1e18;
const int N = 1e5 + 5;
const int MAXM = 2e6 + 5;
const int modulo = 1000000007;
const int L = 25;
vector<int>adj[N];
int dm[N], pf[N];
int up[L][N];

void dfs(int v, int s = 0)
{
    for(int i = 1; i < L; ++i)
        up[i][v] = up[i - 1][up[i - 1][v]];
    pf[v] = s;
    for(auto u : adj[v]){
        up[0][u] = v;
        dfs(u, s + dm[u]);
    }
}

void solve(int test_case) {
    int n, q;
    cin >> n >> q;
    vector<pair<int,int>>a;
    for(int i = 1; i<=n; ++i){
        int v, c;
        cin >> v >> c;
        dm[i] = c;
        a.push_back({v, i});
    }

    sort(all(a), [&](pair<int,int>& l, pair<int,int>& r)
    {
        if(l.first != r.first)
            return l.first < r.first;
        return l.second > r.second;
    });

    set<int>rs= {n + 1};
    for(auto it = a.rbegin(); it != a.rend(); ++it)
    {
        int v = it -> second;
        int u = *rs.upper_bound(v);
        adj[u].push_back(v);
        rs.insert(v);
    }
    dfs(n + 1);

    while(q--)
    {
        int r, v;
        cin >> r >> v;
        int s = pf[r];
        for(int i = L - 1; i >= 0; --i)
        {
            int p = up[i][r];
            if(s - pf[p] + dm[p] < v)
                r = up[i][r];
        }
        if(s - pf[r] + dm[r] < v)
            r = up[0][r];
        cout << r % (n + 1) << endll;
    }
}





main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    for(int i = 1; i <= t; ++i)
        solve(i);
    return 0;
}

Compilation message

fountain.cpp:160:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  160 | main() {
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23640 KB Output is correct
2 Correct 3 ms 23644 KB Output is correct
3 Correct 3 ms 23644 KB Output is correct
4 Correct 3 ms 23644 KB Output is correct
5 Correct 3 ms 23900 KB Output is correct
6 Correct 4 ms 23900 KB Output is correct
7 Correct 4 ms 23896 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 42288 KB Output is correct
2 Correct 159 ms 41156 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23640 KB Output is correct
2 Correct 3 ms 23644 KB Output is correct
3 Correct 3 ms 23644 KB Output is correct
4 Correct 3 ms 23644 KB Output is correct
5 Correct 3 ms 23900 KB Output is correct
6 Correct 4 ms 23900 KB Output is correct
7 Correct 4 ms 23896 KB Output is correct
8 Correct 166 ms 42288 KB Output is correct
9 Correct 159 ms 41156 KB Output is correct
10 Correct 4 ms 23896 KB Output is correct
11 Correct 100 ms 30416 KB Output is correct
12 Correct 217 ms 44748 KB Output is correct
13 Correct 199 ms 38084 KB Output is correct
14 Correct 179 ms 36292 KB Output is correct
15 Correct 128 ms 35272 KB Output is correct