Submission #1045208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045208		MrPavlito	Fountain (eJOI20_fountain)	C++17	0 / 100	82 ms	33724 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));
        for(int i=0; i<n; i++)
        {
            cin >> niz[i].fi >> niz[i].sc;
            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;
            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>=1; i--)
            {
                if(a==-1)break;
                if(sm[i][a] < b)
                {
                    b-= sm[i][a];
                    a = nxt[i-1][a];
                }
                else continue;
            }
            if(a==-1)rez = -1;
            else rez = nxt[0][a];
            cout << rez + 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:43:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |                 int mid = l+r>>1;
      |                           ~^~

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