Submission #421165

#TimeUsernameProblemLanguageResultExecution timeMemory
421165PbezzHorses (IOI15_horses)C++14
0 / 100
74 ms28148 KiB
#include "horses.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define ll long long #define pb push_back typedef pair<ll,ll> pii; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; const ll MAXN=5e5+5; const ll MOD=1e9+7; int x[MAXN],y[MAXN],mini,n; pair<ll,bool> seg[4*MAXN]; //seg[node].second = 1 se ja ultrapassou 1e9+7 void recalculate(ll node){ bool ok=false; if(seg[2*node+1].second==true)ok=true; if(seg[2*node+2].second==true)ok=true; ll res = seg[2*node+1].first*seg[2*node+2].first; if(res>=MOD){ res%=MOD; ok=true; } seg[node] = {res,ok}; } void build(ll node, ll left, ll right){ if(left==right){ seg[node] = {(ll)x[left],false}; }else{ ll middle=(left+right)/2; build(2*node+1,left,middle); build(2*node+2,middle+1,right); recalculate(node); } } void update(ll node, ll left, ll right, ll pos, ll val){ if(left==right){ seg[node]={val,false}; }else{ ll middle = (left+right)/2; if(pos<=middle)update(2*node+1,left,middle,pos,val); if(pos>=middle+1)update(2*node+2,middle+1,right,pos,val); recalculate(node); } } ll querie(ll node, ll left, ll right, ll a, ll b){ if(a<=left&&b>=right){ return seg[node].first; }else{ ll middle=(left+right)/2,res=1; if(a<=middle)res*=querie(2*node+1,left,middle,a,b); res%=MOD; if(b>=middle+1)res*=querie(2*node+2,middle+1,right,a,b); res%=MOD; if(res<0)res+=MOD; return res; } } int init(int N, int X[], int Y[]){ ll i,j=N; mini=MOD+10; n=N; for(i=0;i<N;i++){ x[i+1] = X[i]; y[i+1] = Y[i]; mini = min(mini,X[i]); } build(0,1,N); ll cur=(ll)x[n]; for(i=N-1;i>=1;i--){ if(cur>=MOD)break; if(y[i]>cur*y[j]){ j=i; }else{ cur*=x[i]; } } ll ans = querie(0,1,N,1,j); ans*=y[j]; ans%=MOD; if(ans<0)ans+=MOD; return ans; } int updateX(int pos, int val){ mini=min(mini,val); //if(mini>=2){ //e otimal ir ate um dos ultimos 30 dias //} update(0,1,n,pos+1,val); x[pos+1]=val; ll i,j=n,cur=(ll)x[n]; for(i=n-1;i>=1;i--){ if(cur>=MOD)break; if(y[i]>cur*y[j]){ j=i; }else{ cur*=x[i]; } } ll ans = querie(0,1,n,1,j); ans*=y[j]; ans%=MOD; if(ans<0)ans+=MOD; return ans; } int updateY(int pos, int val) { y[pos+1]=val; ll i,j=n,cur=(ll)x[n]; for(i=n-1;i>=1;i--){ if(cur>=MOD)break; if(y[i]>cur*y[j]){ j=i; }else{ cur*=x[i]; } } ll ans = querie(0,1,n,1,j); ans*=y[j]; ans%=MOD; if(ans<0)ans+=MOD; return ans; }

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:119:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:153:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  153 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:179:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  179 |  return ans;
      |         ^~~
#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...