oj.uz

답안 #1009002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009002 2024-06-27T07:44:10 Z modwwe Fountain (eJOI20_fountain) C++17
100 / 100
 111 ms 18908 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: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]);
      |           ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 17644 KB Output is correct
2 Correct 85 ms 17620 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 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