oj.uz

Submission #782945

# Submission time Handle Problem Language Result Execution time Memory
782945 2023-07-14T11:53:13 Z HoriaHaivas Fountain (eJOI20_fountain) C++14
100 / 100
 145 ms 10204 KB 
/*
    "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

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.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7348 KB Output is correct
2 Correct 106 ms 7868 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 93 ms 7348 KB Output is correct
9 Correct 106 ms 7868 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 58 ms 4556 KB Output is correct
12 Correct 145 ms 10204 KB Output is correct
13 Correct 137 ms 9124 KB Output is correct
14 Correct 92 ms 8328 KB Output is correct
15 Correct 98 ms 8592 KB Output is correct