Submission #783856

#	Time	Username	Problem	Language	Result	Execution time	Memory
783856		AndrijaM	Fountain (eJOI20_fountain)	C++14	60 / 100	321 ms	5376 KiB

fountain

#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]+y;
        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;
                }
            }
            if(sum[n]-sum[x-1]<y)
            {
                l=0;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

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