Submission #43563

#TimeUsernameProblemLanguageResultExecution timeMemory
43563PowerOfNinjaGoHorses (IOI15_horses)C++14
17 / 100
1434 ms73556 KiB
//Power Of Ninja Go #include <bits/stdc++.h> #ifdef atom #include "grader.cpp" #else #include "horses.h" #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vii vector< ii > #define pb push_back const int maxn = 500005; const int md = 1e9 + 7; ll prod[4*maxn]; ll most[4*maxn]; int x[4*maxn]; int y[4*maxn]; int n; int mul(ll a, ll b) { a %= md; b %= md; return (1LL*a*b)%md; } void update(ll *st, int x, int dx, int md, int p = 1, int L = 1, int R = n) { if(L> x || R< x) return; if(L == R && L == x) { st[p] = dx; return; } int M = (L+R)/2; //printf("%d %d %d\n", L, R, M); //system("pause"); update(st, x, dx, md, 2*p, L, M); update(st, x, dx, md, 2*p+1, M+1, R); if(md == 1) st[p] = mul(st[2*p], st[2*p+1]); else st[p] = max(st[2*p], st[2*p+1]); } ll ask(ll *st, int i, int j, int md, int p = 1, int L = 1, int R = n) { if(i> R || j< L) return 1; if(i<= L && R<= j) return st[p]; int M = (L+R)/2; ll x = ask(st, i, j, md, 2*p, L, M); ll y = ask(st, i, j, md, 2*p+1, M+1, R); if(md == 1) return mul(x, y); else return max(x, y); } set<int> bst; int query() { vi tmp; ll product = 1; for(auto it = bst.rbegin(); it != bst.rend() && product<1e9; it++) { tmp.pb(*it); product *= x[*it]; } reverse(tmp.begin(), tmp.end()); if(tmp.empty()) return ask(most, 1, n, 2); ll best = ask(most, 1, tmp[0]-1, 2); ll run = 1; int q = tmp.size(); for(int i = 0; i< q; i++) { //printf("%d", tmp[i]); run *= x[tmp[i]]; int rend = i+1<q?tmp[i+1]:n+1; best = max(best, 1LL*run*ask(most, tmp[i], rend-1, 2)); //printf("(%lld)", run*ask(most, tmp[i], rend-1, 2)); } //best %= md; return mul(best, ask(prod, 1, tmp[0]-1, 1)); } int init(int N, int X[], int Y[]) { n = N; for(int i = 1; i<= n; i++) x[i] = X[i-1], y[i] = Y[i-1]; for(int i = 1; i<= N; i++) update(prod, i, x[i], 1); for(int i = 1; i<= N; i++) update(most, i, y[i], 2); for(int i = 1; i<= N; i++) if(x[i]> 1) bst.insert(i); return query(); } int updateX(int pos, int val) { pos++; x[pos] = val; if(val> 1) bst.insert(pos); else bst.erase(pos); update(prod, pos, val, 1); return query(); } int updateY(int pos, int val) { pos++; y[pos] = val; update(most, pos, val, 2); return query(); }

Compilation message (stderr)

horses.cpp: In function 'int mul(ll, ll)':
horses.cpp:25:19: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (1LL*a*b)%md;
                   ^
horses.cpp: In function 'void update(ll*, int, int, int, int, int, int)':
horses.cpp:27:75: warning: declaration of 'md' shadows a global declaration [-Wshadow]
 void update(ll *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
                                                                           ^
horses.cpp:16:11: note: shadowed declaration is here
 const int md = 1e9 + 7;
           ^
horses.cpp:27:75: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update(ll *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
                                                                           ^
horses.cpp:19:5: note: shadowed declaration is here
 int x[4*maxn];
     ^
horses.cpp: In function 'll ask(ll*, int, int, int, int, int, int)':
horses.cpp:42:69: warning: declaration of 'md' shadows a global declaration [-Wshadow]
 ll ask(ll *st, int i, int j, int md, int p = 1, int L = 1, int R = n)
                                                                     ^
horses.cpp:16:11: note: shadowed declaration is here
 const int md = 1e9 + 7;
           ^
horses.cpp:47:5: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  ll x = ask(st, i, j, md, 2*p, L, M);
     ^
horses.cpp:19:5: note: shadowed declaration is here
 int x[4*maxn];
     ^
horses.cpp:48:5: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  ll y = ask(st, i, j, md, 2*p+1, M+1, R);
     ^
horses.cpp:20:5: note: shadowed declaration is here
 int y[4*maxn];
     ^
horses.cpp: In function 'int query()':
horses.cpp:63:42: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  if(tmp.empty()) return ask(most, 1, n, 2);
                                          ^
horses.cpp:66:19: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int q = tmp.size();
                   ^
#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...