제출 #382904

#제출 시각아이디문제언어결과실행 시간메모리
382904blacktulipFountain (eJOI20_fountain)C++17
0 / 100
318 ms50304 KiB
#include <bits/stdc++.h> using namespace std; typedef long long lo; typedef pair< lo,lo > PII; #define fi first #define se second #define mp make_pair #define endl "\n" #define int long long #define pb push_back #define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define FOR for(int i=1;i<=n;i++) #define mid ((start+end)/2) const lo inf = 1000000000; const lo KOK = 100000; const lo LOG = 30; const lo li = 500005; const lo mod = 1000000007; int n,m,b[li],a[li],k,flag,t,fa[li][30],sum[li][30],dp[li]; inline void build_lca(){ for(int j=1;j<=27;j++){ for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; sum[i][j]=sum[i][j-1]+sum[fa[i][j-1]][j-1]; } } } int32_t main(void){ scanf("%lld %lld",&n,&t); FOR{ scanf("%lld %lld",&a[i],&b[i]); } stack<pair<int,int>> st; for(int i=n;i>=1;i--){ while(st.size() && st.top().fi<=a[i]){ st.pop(); } if(st.size())dp[i]=st.top().se; else dp[i]=n+1; st.push({a[i],i}); //~ cout<<dp[i]<<" **\n"; } FOR{ fa[i][0]=dp[i]; sum[i][0]=b[dp[i]]; } build_lca(); while(t--){ int x,y; scanf("%lld %lld",&x,&y); if(b[x]>=y){printf("%lld\n",x);continue;} y-=b[x]; //~ cout<<y<<" :: \n"; for(int i=27;i>=0;i--){ if(sum[x][i]<=y){ y-=sum[x][i]; x=fa[x][i]; //~ cout<<y<<" :: \n"; } } for(int i=0;i<=27;i++){ if(sum[x][i]>=y){ y-=sum[x][i]; x=fa[x][i]; //~ cout<<y<<" :: \n"; break; } } if(y>0){ printf("0\n"); continue; } printf("%lld\n",x); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

fountain.cpp: In function 'int32_t main()':
fountain.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf("%lld %lld",&n,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
fountain.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   scanf("%lld %lld",&a[i],&b[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%lld %lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...