Submission #782945

#	Time	Username	Problem	Language	Result	Execution time	Memory
782945		HoriaHaivas	Fountain (eJOI20_fountain)	C++14	100 / 100	145 ms	10204 KiB

fountain

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct qq
{
    int r;
    int v;
    int pos;
    int ans;
};

bool cmp(qq a, qq b)
{
     return a.r>b.r;
}

bool cmp2(qq a, qq b)
{
     return a.pos<b.pos;
}

qq query[200001];
int d[100001];
int c[100001];
int aib[100001];
int st[100001];
int t;

void update(int index, int delta)
{
     while (index>0)
     {
           aib[index]+=delta;
           index-=index&(-index);
     }
}

int prefsum(int index)
{
    int sum;
    sum=0;
    while (index<=t)
    {
         sum+=aib[index];
         index+=index&(-index);
    }
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,cnt,pas,ree;
    cin >> n >> q;
    for (i=1;i<=n;i++)
    {
         cin >> d[i] >> c[i];
    }
    for (i=1;i<=q;i++)
    {
         cin >> query[i].r >> query[i].v;
         query[i].pos=i;
    }
    sort(query+1,query+1+q,cmp);
    t=0;
    cnt=1;
    for (i=n;i>=1;i--)
    {
         if (t==0 || d[i]<d[st[t]])
         {
             t++;
             st[t]=i;
             update(t,c[i]);
         }
         else
         {
             while (d[i]>=d[st[t]] && t>0)
             {
                  update(t,-c[st[t]]);
                  t--;
             }
             t++;
             st[t]=i;
             update(t,c[i]);
         }
         while (query[cnt].r==i)
         {
                ree=t+1;
                pas=(1<<16);
                while (pas)
                {
                    if (ree-pas>0 && prefsum(ree-pas)<query[cnt].v)
                        ree-=pas;
                    pas=pas/2;
                }
                ree--;
                query[cnt].ans=st[ree];
                cnt++;
         }
    }
    sort(query+1,query+1+q,cmp2);
    for (i=1;i<=q;i++)
    {
         cout << query[i].ans << "\n";
    }
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:63:15: warning: unused variable 'j' [-Wunused-variable]
   63 |     int n,q,i,j,cnt,pas,ree;
      |               ^

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