oj.uz

Submission #783846

# Submission time Handle Problem Language Result Execution time Memory
783846 2023-07-15T11:24:04 Z AndrijaM Fountain (eJOI20_fountain) C++14
30 / 100
 266 ms 2176 KB 
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,q;
    cin>>n>>q;
    vector<pair<int,int>>v;
    int sum[n+1];
    sum[0]=0;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        sum[i+1]=sum[i]+x;
        v.push_back({x,y});
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(n<=1005)
        {
            x--;
            int d=v[x].first;///x-1
            y-=v[x].second;
            if(y>0)
            x++;
            if(y>0)
            while(true)
            {
                if(x>=n)
                {
                    break;
                }
                if(d<v[x].first)
                {
                    y-=v[x].second;
                    d=v[x].first;
                }
                if(y<=0)break;
                x++;
            }
            x++;
            if(x>n)x=0;
            cout<<x<<endl;
        }
        else
        {
            int l=x;
            int r=n;
            while(l<r)
            {
                int mid=l+(r-l)/2;
                if(sum[mid]-sum[x-1]<y)
                {
                    l=mid+1;
                }
                if(sum[mid]-sum[x-1]>=y)
                {
                    r=mid;
                }
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 4 ms 212 KB Output is correct
6 Correct 5 ms 212 KB Output is correct
7 Correct 4 ms 212 KB Output is correct
8 Incorrect 266 ms 2176 KB Output isn't correct
9 Halted 0 ms 0 KB -