제출 #389189

#제출 시각아이디문제언어결과실행 시간메모리
389189PedroBigMan말 (IOI15_horses)C++14
100 / 100
1457 ms236128 KiB
#include "horses.h" /* Author of all code: Pedro BIGMAN Dias Last edit: 15/02/2021 */ #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <list> #include <iomanip> #include <stdlib.h> #include <time.h> #include <cstring> using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef long double ld; #define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++) #define pb push_back #define mp make_pair #define pl pair<ll,ll> #define ff first #define ss second #define whole(x) x.begin(),x.end() #define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl #define INF 500000000LL #define EPS 0.00000001 #define pi 3.14159 ll mod=1000000007LL; template<class A=ll> void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;} template<class A=ll> void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} ll fastexp(ll a,ll e) { if(e==0) {return 1LL;} if(e%2LL==0) { ll v=fastexp(a,(ll) e/2LL); return (v*v)%mod; } else { ll v=fastexp(a,(ll) e/2LL); return (((v*v)%mod)*a)%mod; } } ll inv(ll s) //assumes mod is prime { return fastexp(s,mod-2LL); } class ST1 { public: ll N; class SV //seg value { public: ld a; ll pos; SV() {a=-((ld) INF);} SV(ld x) {a=x;} SV operator & (SV X) { SV ANS(max(a,X.a)); if(a>X.a) {ANS.pos=pos;} else {ANS.pos=X.pos;} return ANS; } }; class LV //lazy value { public: ld a; LV() {a=0.0;} LV(ld x) {a=x;} LV operator & (LV X) {LV ANS(a+X.a); return ANS;} }; SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node { SV X(p[c].a+lazy[c].a); X.pos=p[c].pos; return X; } SV neuts; LV neutl; vector<SV> p; vector<LV> lazy; vector<pl> range; ST1() {N=0LL;} ST1(vector<ld> arr) { N = (ll) 1<<(ll) ceil(log2(arr.size())); REP(i,0,2*N) {range.pb(mp(0LL,0LL));} REP(i,0,N) {p.pb(neuts);} REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i); p[i+N].pos=i;} REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i); p[i+N].pos=i;} ll cur = N-1; while(cur>0) { p[cur]=p[2*cur]&p[2*cur+1]; range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss); cur--; } REP(i,0,2*N) {lazy.pb(neutl);} } void prop(ll c) //how lazy values propagate { lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1]; lazy[c]=neutl; } SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b) { ll x=range[c].ff; ll y=range[c].ss; if(y<a || x>b) {return neuts;} if(x>=a && y<=b) {return upval(c);} prop(c); p[c]=upval(c); SV ans = query(a,b,2*c)&query(a,b,2*c+1); return ans; } void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b) { ll x=range[c].ff; ll y=range[c].ss; if(y<a || x>b) {return ;} if(x>=a && y<=b) { lazy[c]=s&lazy[c]; return; } prop(c); update(s,a,b,2*c); update(s,a,b,2*c+1); p[c]=upval(2*c)&upval(2*c+1); } }; class ST2 { public: ll N; class SV //seg value { public: ll a; SV() {a=1LL;} SV(ll x) {a=x;} SV operator & (SV X) {SV ANS((a*X.a)%mod); return ANS;} }; class LV //lazy value { public: ll a; LV() {a=1LL;} LV(ll x) {a=x;} LV operator & (LV X) {LV ANS((a*X.a)%mod); return ANS;} }; SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node { SV X((p[c].a*fastexp(lazy[c].a,(range[c].ss-range[c].ff+1)))%mod); return X; } SV neuts; LV neutl; vector<SV> p; vector<LV> lazy; vector<pl> range; ST2() {N=0LL;} ST2(vector<ll> arr) { N = (ll) 1<<(ll) ceil(log2(arr.size())); REP(i,0,2*N) {range.pb(mp(0LL,0LL));} REP(i,0,N) {p.pb(neuts);} REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);} REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);} ll cur = N-1; while(cur>0) { p[cur]=p[2*cur]&p[2*cur+1]; range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss); cur--; } REP(i,0,2*N) {lazy.pb(neutl);} } void prop(ll c) //how lazy values propagate { lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1]; lazy[c]=neutl; } SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b) { ll x=range[c].ff; ll y=range[c].ss; if(y<a || x>b) {return neuts;} if(x>=a && y<=b) {return upval(c);} prop(c); p[c]=upval(c); SV ans = query(a,b,2*c)&query(a,b,2*c+1); return ans; } void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b) { ll x=range[c].ff; ll y=range[c].ss; if(y<a || x>b) {return ;} if(x>=a && y<=b) { lazy[c]=s&lazy[c]; return; } prop(c); update(s,a,b,2*c); update(s,a,b,2*c+1); p[c]=upval(2*c)&upval(2*c+1); } }; ll N; vector<ld> ps; vector<ll> X; vector<ll> Y; ST1 A; ST2 B; int solve() { ll ind = A.query(0,N-1).pos; ll ans = B.query(0,ind).a; ans*=Y[ind]; ans%=mod; if(ans<0LL) {ans+=mod;} int x = (int) ans; return x; } int init(int n, int x[], int y[]) { N=(ll) n; REP(i,0,N) {X.pb((ll) x[i]); Y.pb((ll) y[i]);} vector<ld> ps; ld sum=(ld) 0.0; ld val1,val2; REP(i,0,N) { val1 = (ld) log2((ld) X[i]); val2 = (ld) log2((ld) Y[i]); sum+=val1; ps.pb(sum+val2); } ST1 initA(ps); A=initA; ST2 initB(X); B=initB; return solve(); } int updateX(int pos, int v) { ll newX = (ll) v; ll oldX = X[pos]; X[pos]=newX; ll val1 = (newX*inv(oldX))%mod; B.update(val1,pos,pos); ld val2 = (ld) log2((ld) newX) - (ld) log2((ld) oldX); A.update(val2,pos,N-1); return solve(); } int updateY(int pos, int v) { ll oldY = Y[pos]; ll newY = (ll) v; Y[pos] = newY; ld val = (ld) log2((ld) newY) - (ld) log2((ld) oldY); A.update(val,pos,pos); return solve(); }

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:258:13: warning: declaration of 'ps' shadows a global declaration [-Wshadow]
  258 |  vector<ld> ps; ld sum=(ld) 0.0;
      |             ^~
horses.cpp:241:12: note: shadowed declaration is here
  241 | vector<ld> ps;
      |            ^~
#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...