oj.uz

Submission #1008999

# Submission time Handle Problem Language Result Execution time Memory
1008999 2024-06-27T07:42:51 Z modwwe Fountain (eJOI20_fountain) C++17
100 / 100
 109 ms 31520 KB 
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
///     fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
int bit[100001];
ib st[17][100001];
ib a[100001];
 vector<int> v;
 void upd(int x,int y)
 {
     for(x;x;x-=x&-x) bit[x]=y;
 }
 int get(int x)
 {
     int s=n+1;
      for(x;x<=n;x+=x&-x) s=min(s,bit[x]);
  return s;
 }
 void setup()
 {
      for(int i=n;i>=1;--i)
      { a[i].a=lower_bound(v.begin(),v.end(),a[i].a)-v.begin()+1;
          s2=get(a[i].a+1);
          st[0][i].a=s2;
           st[0][i].b=a[i].b;
       upd(a[i].a,i);}
 }
void phongbeo()
{
     cin>>n>>m;
      for(int i=1;i<=n;i++)
         cin>>a[i].a>>a[i].b,bit[i]=n+1,v.pb(a[i].a);
          sort(v.begin(),v.end());
setup();
st[0][n+1]={n+1,0};
for(int i=1;i<17;i++)
    for(int j=1;j<=n;j++)
    st[i][j].a=st[i-1][st[i-1][j].a].a,
    st[i][j].b=st[i-1][j].b+st[i-1][st[i-1][j].a].b;
while(m--)
{
     cin>>l>>r ;
      for(int i=16;i>=0;--i)
        if(st[i][l].b<r)
      {
          r-=st[i][l].b;
           l=st[i][l].a;
           if(l==n+1)
           {
               break;
           }
      }
      if(l==n+1) cout<<0;
 else cout<<l;
  down
}

}

Compilation message

fountain.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main()
      | ^~~~
fountain.cpp: In function 'void upd(long long int, long long int)':
fountain.cpp:63:10: warning: statement has no effect [-Wunused-value]
   63 |      for(x;x;x-=x&-x) bit[x]=y;
      |          ^
fountain.cpp: In function 'long long int get(long long int)':
fountain.cpp:68:11: warning: statement has no effect [-Wunused-value]
   68 |       for(x;x<=n;x+=x&-x) s=min(s,bit[x]);
      |           ^

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 30880 KB Output is correct
2 Correct 85 ms 30924 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29016 KB Output is correct
2 Correct 3 ms 29020 KB Output is correct
3 Correct 3 ms 29180 KB Output is correct
4 Correct 4 ms 29020 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 4 ms 29020 KB Output is correct
7 Correct 3 ms 29020 KB Output is correct
8 Correct 82 ms 30880 KB Output is correct
9 Correct 85 ms 30924 KB Output is correct
10 Correct 3 ms 29020 KB Output is correct
11 Correct 52 ms 30364 KB Output is correct
12 Correct 109 ms 31520 KB Output is correct
13 Correct 96 ms 31432 KB Output is correct
14 Correct 73 ms 31440 KB Output is correct
15 Correct 73 ms 31476 KB Output is correct