Submission #1045270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045270		MrPavlito	Fountain (eJOI20_fountain)	C++17	100 / 100	194 ms	41220 KiB

fountain

#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 (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40