제출 #345027

#제출 시각아이디문제언어결과실행 시간메모리
345027ogibogi2004말 (IOI15_horses)C++14
100 / 100
470 ms48876 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; #define y1 da #define y2 ne #define ll long long const int MAXN=5e6+6; const ll MOD=1e9+7; int x1[MAXN],y1[MAXN]; ll fastpow(ll x,ll p) { if(p==0)return 1; if(p==1)return x; //if(p==2)return (x*x)%MOD; ll t=fastpow(x,p/2); t*=t;t%=MOD; if(p%2==1)t*=x; t%=MOD; return t; } ll inverse(ll x) { return fastpow(x,MOD-2); } set<int>notones; int treeX[4*MAXN],treeY[4*MAXN]; void updateY(int idx,int l,int r,int q,int val) { if(l>q||r<q)return; if(l==r) { treeY[idx]=val; return; } int mid=(l+r)/2; if(mid>=q)updateY(idx*2,l,mid,q,val); else updateY(idx*2+1,mid+1,r,q,val); treeY[idx]=max(treeY[idx*2],treeY[idx*2+1]); } int n; int queryY(int idx,int l,int r,int ql,int qr) { if(l>qr)return 0; if(r<ql)return 0; if(l>=ql&&r<=qr)return treeY[idx]; int mid=(l+r)/2; if(mid+1>qr)return queryY(idx*2,l,mid,ql,qr); if(mid<ql)return queryY(idx*2+1,mid+1,r,ql,qr); return max(queryY(idx*2,l,mid,ql,qr),queryY(idx*2+1,mid+1,r,ql,qr)); } void updateX(int idx,int l,int r,int q,int val) { if(l>q||r<q)return; if(l==r) { treeX[idx]=val; return; } int mid=(l+r)/2; if(mid>=q)updateX(idx*2,l,mid,q,val); else updateX(idx*2+1,mid+1,r,q,val); treeX[idx]=((ll)treeX[idx*2]*treeX[idx*2+1])%MOD; } int queryX(int idx,int l,int r,int ql,int qr) { if(l>qr)return 1; if(r<ql)return 1; if(l>=ql&&r<=qr)return treeX[idx]; int mid=(l+r)/2; if(mid+1>qr)return queryX(idx*2,l,mid,ql,qr); if(mid<ql)return queryX(idx*2+1,mid+1,r,ql,qr); return ((ll)queryX(idx*2,l,mid,ql,qr)*queryX(idx*2+1,mid+1,r,ql,qr))%MOD; } ll prodall=1; ll solve() { notones.insert(0); int last=n; auto it=notones.end();--it; ll d1=1; pair<ll,ll>ans; ans={-1,-1}; ll y2,cnt=0; for(;;--it) { cnt++; ll y1=queryY(1,0,n-1,(*it),last-1); if(ans.first==-1) { y2=y1; ans.first=y1; ans.second=d1; } else if(ans.first*d1<y1*ans.second) { ans.first=y1;y2=y1; ans.second=d1; } //if(cnt>50)break; if(it==notones.begin())break; last=(*it);d1=(ll)d1*x1[(*it)]; if(d1>(ll)1e9)break; //if(d1>(ll)1e9*ans.second/ans.first)break; } /*if(d1<=(ll)1e9&&ans.first*d1<ico*ans.second) { return ico; }*/ /*it=notones.end();--it; last=n; for(;;--it) { --j; if(j==0) { //cout<<queryX(1,0,n-1,0,(*it))<<" "<<queryY(1,0,n-1,(*it),last-1)<<endl; return ((ll)queryX(1,0,n-1,0,(*it))*queryY(1,0,n-1,(*it),last-1))%MOD; } last=(*it); }*/ ll f=prodall; f*=inverse(ans.second); f%=MOD; return (f*y2)%MOD; return 0; } int init(int N, int X[], int Y[]) { n=N; for(int i=0;i<N;++i) { x1[i]=X[i]; y1[i]=Y[i]; prodall*=x1[i];prodall%=MOD; if(X[i]>1) { notones.insert(i); } //updateX(1,0,N-1,i,X[i]); } for(int i=0;i<N;++i) { updateY(1,0,N-1,i,Y[i]); } return solve(); } int updateX(int pos, int val) { prodall*=inverse(x1[pos]);prodall%=MOD; x1[pos]=val; prodall*=x1[pos];prodall%=MOD; if(val==1) { notones.erase(pos); } else notones.insert(pos); //updateX(1,0,n-1,pos,x1[pos]); return solve(); } int updateY(int pos, int val) { y1[pos]=val; updateY(1,0,n-1,pos,y1[pos]); return solve(); }

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

horses.cpp: In function 'void updateX(int, int, int, int, int)':
horses.cpp:63:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |  treeX[idx]=((ll)treeX[idx*2]*treeX[idx*2+1])%MOD;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int queryX(int, int, int, int, int)':
horses.cpp:73:70: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |  return ((ll)queryX(idx*2,l,mid,ql,qr)*queryX(idx*2+1,mid+1,r,ql,qr))%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:4:12: warning: declaration of 'da' shadows a global declaration [-Wshadow]
    4 | #define y1 da
      |            ^~
horses.cpp:88:6: note: in expansion of macro 'y1'
   88 |   ll y1=queryY(1,0,n-1,(*it),last-1);
      |      ^~
horses.cpp:4:12: note: shadowed declaration is here
    4 | #define y1 da
      |            ^~
horses.cpp:9:14: note: in expansion of macro 'y1'
    9 | int x1[MAXN],y1[MAXN];
      |              ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:145:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  145 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:158:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:164:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  164 |  return solve();
      |         ~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...