Submission #199715

#TimeUsernameProblemLanguageResultExecution timeMemory
199715FieryPhoenixHorses (IOI15_horses)C++11
17 / 100
364 ms54124 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstdio> #include <map> #include <queue> #include <set> #include <iomanip> #include <deque> #include <cassert> #include <ctime> #include <cstring> #include <cstdlib> #include <chrono> #include <ctime> #include <random> #include <stack> #include <unordered_set> #include <unordered_map> #include <iterator> #include <climits> #include <horses.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000007 int N; ll worth[1005],X[500001],Y[500001]; bool over[1005]; set<int>bigInd; ll treeMax[1000001],treeMult[1000001]; void updateMax(int pos, int val){ pos+=N; treeMax[pos]=val; for (pos/=2;pos>=1;pos/=2) treeMax[pos]=max(treeMax[pos*2],treeMax[pos*2+1]); } ll queryMax(int L, int R){ L+=N; R+=N; ll ans=0; while (L<=R){ if (L%2==1) ans=max(ans,treeMax[L++]); if (R%2==0) ans=max(ans,treeMax[R--]); L/=2; R/=2; } return ans; } void updateMult(int pos, int val){ pos+=N; treeMult[pos]=val; for (pos/=2;pos>=1;pos/=2) treeMult[pos]=(treeMult[pos*2]*treeMult[pos*2+1])%MOD; } int queryMult(int L, int R){ L+=N; R+=N; ll ans=1; while (L<=R){ if (L%2==1) ans*=treeMult[L++]; if (R%2==0) ans*=treeMult[R--]; ans%=MOD; L/=2; R/=2; } return ans; } int calc(){ if (bigInd.size()==0) return queryMax(0,N-1); vector<int>v; set<int>::iterator it=bigInd.end(); it--; for (;;){ v.push_back(*it); if (it==bigInd.begin() || v.size()==30) break; it--; } reverse(v.begin(),v.end()); int M=v.size(); for (int i=0;i<=M;i++){ worth[i]=0; over[i]=false; } for (int i=M-1;i>=0;i--){ if (over[i+1]) worth[i]=X[v[i]]*worth[i+1]; else{ int L=v[i]; int R; if (i==M-1) R=N-1; else R=v[i+1]-1; worth[i]=X[v[i]]*max(queryMax(L,R),worth[i+1]); } over[i]=(worth[i]>1000000000) | over[i+1]; if (over[i]) worth[i]%=MOD; } return (worth[0]*queryMult(0,v[0]-1))%MOD; } int init(int n, int x[], int y[]){ N=n; for (int i=0;i<N;i++){ X[i]=x[i]; Y[i]=y[i]; updateMax(i,Y[i]); updateMult(i,X[i]); if (X[i]>1) bigInd.insert(i); } return calc(); } int updateX(int pos, int val){ if (X[pos]>1 && val==1) bigInd.erase(pos); else if (X[pos]==1 && val>1) bigInd.insert(pos); X[pos]=val; updateMult(pos,val); return calc(); } int updateY(int pos, int val){ Y[pos]=val; updateMax(pos,val); return calc(); }

Compilation message (stderr)

horses.cpp: In function 'int queryMult(int, int)':
horses.cpp:78:10: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return ans;
          ^~~
horses.cpp: In function 'int calc()':
horses.cpp:83:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return queryMax(0,N-1);
            ~~~~~~~~^~~~~~~
horses.cpp:94:15: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   int M=v.size();
         ~~~~~~^~
horses.cpp:115:40: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return (worth[0]*queryMult(0,v[0]-1))%MOD;
                                        ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:123:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateMax(i,Y[i]);
                 ~~~^
horses.cpp:124:21: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     updateMult(i,X[i]);
                  ~~~^
#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...