oj.uz

Submission #1045235

# Submission time Handle Problem Language Result Execution time Memory
1045235 2024-08-05T19:18:02 Z MrPavlito Fountain (eJOI20_fountain) C++17
30 / 100
 166 ms 34292 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));
        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>=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:43:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |                 int mid = l+r>>1;
      |                           ~^~
fountain.cpp:78:17: warning: unused variable 'rez' [-Wunused-variable]
   78 |             int rez = a;
      |                 ^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 33760 KB Output is correct
2 Correct 166 ms 34292 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -