//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:19:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
19 | const int inf=1e18;
| ^~~~
fountain.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
47 | main()
| ^~~~
fountain.cpp: In function 'void upd(int, 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 'int get(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]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
17644 KB |
Output is correct |
| 2 |
Correct |
85 ms |
17620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 8 |
Correct |
70 ms |
17644 KB |
Output is correct |
| 9 |
Correct |
85 ms |
17620 KB |
Output is correct |
| 10 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 11 |
Correct |
48 ms |
15880 KB |
Output is correct |
| 12 |
Correct |
111 ms |
18908 KB |
Output is correct |
| 13 |
Correct |
108 ms |
18796 KB |
Output is correct |
| 14 |
Correct |
75 ms |
18392 KB |
Output is correct |
| 15 |
Correct |
60 ms |
18384 KB |
Output is correct |
