oj.uz

Submission #1045270

# Submission time Handle Problem Language Result Execution time Memory
1045270 2024-08-05T19:44:49 Z MrPavlito Fountain (eJOI20_fountain) C++17
100 / 100
 194 ms 41220 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const int lg = 20;
const long long inf = 1e18;

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        int n,q;
        cin >> n >> q;
        vector<pii> niz(n);
        vector<int> prefmx(n+1, 0);
        vector<vector<int>>sm(lg, vector<int>(n,0));
        vector<vector<int>>nxt(lg, vector<int>(n,-1));
        priority_queue<pii, vector<pii>,greater<pii>> pq;
        for(int i=0; i<n; i++)
        {
            cin >> niz[i].fi >> niz[i].sc;
            while(!pq.empty() && pq.top().fi < niz[i].fi)
            {
                nxt[0][pq.top().sc] = i;
                pq.pop();
            }
            pq.push(mp(niz[i].fi, i));
            prefmx[i+1] = max(prefmx[i], niz[i].fi);
            sm[0][i] = niz[i].sc;
        }
        /*
        for(int i=0; i<n-1; i++)
        {
            int l = i+1; int r = n-1;
            int rez = n;
            while(l<=r)
            {
                int mid = l+r>>1;
                if(prefmx[mid+1] > niz[i].fi)
                {
                    rez = mid;
                    r = mid-1;
                }
                else
                {
                    l= mid+1;
                }
            }
            if(rez==n)continue;
            nxt[0][i] = rez;
        }
        */
        for(int i=1; i<lg; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(nxt[i-1][j] == -1)nxt[i][j] = -1;
                else nxt[i][j] = nxt[i-1][nxt[i-1][j]];
            }
        }
        for(int i=1; i<lg; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(nxt[i-1][j] == -1)sm[i][j] = sm[i-1][j];
                else sm[i][j] = sm[i-1][j] + sm[i-1][nxt[i-1][j]];
            }
        }
        while(q--)
        {
            int a,b;
            cin >> a >> b;
            a--;
            int rez = a;
            if(b <= niz[a].sc)
            {
                cout << a+1 << endl;
                continue;
            }
            for(int i=lg-1; i>=0; i--)
            {
                if(a==-1)break;
                if(sm[i][a] < b)
                {
                    b-= sm[i][a];
                    a = nxt[i][a];
                }
            }
            cout << a + 1 << endl;
        }
    }
}

/*
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
*/

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:87:17: warning: unused variable 'rez' [-Wunused-variable]
   87 |             int rez = a;
      |                 ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 33900 KB Output is correct
2 Correct 141 ms 31400 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 102 ms 33900 KB Output is correct
9 Correct 141 ms 31400 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 51 ms 21656 KB Output is correct
12 Correct 194 ms 40004 KB Output is correct
13 Correct 130 ms 39744 KB Output is correct
14 Correct 79 ms 39044 KB Output is correct
15 Correct 69 ms 41220 KB Output is correct