Submission #60126

#TimeUsernameProblemLanguageResultExecution timeMemory
60126istleminHorses (IOI15_horses)C++14
100 / 100
902 ms224208 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = a; i<int(b);++i) #define all(v) v.begin(),v.end() #define sz(v) v.size() #define trav(a,c) for(auto a: c) typedef long long ll; typedef vector<ll> vi; typedef pair<ll,ll> pii; ll n; vi x; vi y; ll mod = 1e9+7; class OldNode{ public: ll val = 1; ll dn,up; OldNode *left; OldNode *right; OldNode(ll _dn,ll _up,vi &init){ dn = _dn; up = _up; if(dn+1!=up){ left = new OldNode(dn,(dn+up)/2,init); right = new OldNode((dn+up)/2,up,init); val = (left->val*right->val)%mod; } else { val = init[dn]%mod; } } ll update(ll a,ll v){ if(dn>a||up<=a) return val; if(dn+1==up) { return val = v%mod; } return val = (left->update(a,v)*right->update(a,v))%mod; } ll query(ll a,ll b){ if(dn>=b||up<=a) return 1; if(a<=dn&&up<=b) return val; return (left->query(a,b)*right->query(a,b))%mod; } }; pair<long double,ll> op1(pair<long double,ll> a,long double b){ return {a.first+b,a.second}; } class Node{ public: pair<long double,ll> val = {0,0}; long double toPush = 0; ll dn,up; Node *left; Node *right; Node(ll _dn,ll _up,vector<long double> &init){ dn = _dn; up = _up; if(dn+1!=up){ left = new Node(dn,(dn+up)/2,init); right = new Node((dn+up)/2,up,init); val = max(left->val,right->val); } else { val.second = dn; val.first = init[dn]; } } void push(){ if(dn+1==up) return; left->val=op1(left->val,toPush); right->val=op1(right->val,toPush); left->toPush+=toPush; right->toPush+=toPush; toPush = 0; } pair<long double,ll> update(ll a,ll b,long double v){ if(dn>=b||up<=a) return val; if(a<=dn&&up<=b) { val=op1(val,v); toPush+=v; return val; } push(); return val = max(left->update(a,b,v),right->update(a,b,v)); } pair<long double,ll> query(ll a,ll b){ if(dn>=b||up<=a) return {-1e30,0}; if(a<=dn&&up<=b) return val; push(); return max(left->query(a,b),right->query(a,b)); } }; Node *st; OldNode *stMul; ll getAns(){ ll index = st->query(0,n).second; ll ans = (stMul->query(0,index+1)*y[index])%mod; //cout<<ans<<endl; return ans; } int init(int N, int X[], int Y[]) { n = N; x.resize(n,1); y.resize(n,1); rep(i,0,n) x[i] = X[i]; rep(i,0,n) y[i] = Y[i]; vector<long double> stD(n); stD[0] = log(x[0]); rep(i,1,n) stD[i] = log(x[i]) + stD[i-1]; rep(i,0,n) stD[i] += log(y[i]); st = new Node(0,N,stD); stMul = new OldNode(0,N,x); rep(i,0,n){ //updateX(i,X[i]); //updateY(i,Y[i]); } /*cout<<"#######"<<endl; rep(i,0,n) cout<<x[i]<<" "; cout<<endl; rep(i,0,n) cout<<y[i]<<" "; cout<<endl; rep(i,0,n) cout<<stMul->query(i,i+1)<<" "; cout<<endl; rep(i,0,n) cout<<st->query(i,i+1).first<<" "; cout<<endl; cout<<"#######"<<endl;*/ return getAns(); } int updateX(int pos, int val) { st->update(pos,n,-log((long double)(x[pos]))+log((long double)(val))); stMul->update(pos,val); x[pos] = val; return getAns(); } int updateY(int pos, int val) { st->update(pos,pos+1,-log(y[pos])+log(val)); y[pos] = val; return getAns(); }

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:149:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:156:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:162:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~
#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...