Submission #387156

#TimeUsernameProblemLanguageResultExecution timeMemory
387156alireza_kavianiHorses (IOI15_horses)C++11
37 / 100
393 ms64772 KiB
#include <bits/stdc++.h> #include "horses.h" using namespace std; typedef long long ll; const ll MAXN = 5e5 + 10; const ll MOD = 1e9 + 7; const ll INF = 1e9 + 5; ll n , x[MAXN] , y[MAXN] , mul[MAXN * 2] , mx[MAXN * 2]; set<int , greater<int>> st; void reBuild(int pos){ for(mul[pos + n] = x[pos] , mx[pos + n] = y[pos] , pos += n ; pos /= 2 ;){ mul[pos] = mul[pos * 2] * mul[pos * 2 + 1] % MOD; mx[pos] = max(mx[pos * 2] , mx[pos * 2 + 1]); } } ll getMul(int ql , int qr){ ll ans = 1; for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){ if(ql & 1) ans = ans * mul[ql++] % MOD; if(qr & 1) ans = ans * mul[--qr] % MOD; } return ans; } ll getMax(int ql , int qr){ ll ans = 0; for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){ if(ql & 1) ans = max(ans , mx[ql++]); if(qr & 1) ans = max(ans , mx[--qr]); } return ans; } ll solve(){ ll ans = 0 , cur = n , prv; for(auto it = st.begin() ; it != st.end() ; it++){ if(ans > INF) break; prv = cur; cur = (*it); ans = max(ans , getMax(cur , prv)) * x[cur]; // cout << cur << ' ' << getMax(cur , prv) << endl; } // cout << endl; return ans % MOD * getMul(0 , cur) % MOD; } int init(int N, int X[], int Y[]) { n = N; for(int i = 0 ; i < N ; i++){ mul[i + N] = X[i]; x[i] = X[i]; mx[i + N] = Y[i]; y[i] = Y[i]; if(X[i] >= 2 || i == 0) st.insert(i); } for(int i = N - 1 ; i >= 1 ; i--){ mul[i] = mul[i * 2] * mul[i * 2 + 1] % MOD; mx[i] = max(mx[i * 2] , mx[i * 2 + 1]); } return solve(); } int updateX(int pos, int val) { x[pos] = val; st.erase(pos); reBuild(pos); if(val >= 2) st.insert(pos); return solve(); } int updateY(int pos, int val) { y[pos] = val; reBuild(pos); return solve(); }

Compilation message (stderr)

horses.cpp: In function 'void reBuild(int)':
horses.cpp:15:57: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   15 |  for(mul[pos + n] = x[pos] , mx[pos + n] = y[pos] , pos += n ; pos /= 2 ;){
      |                                                     ~~~~^~~~
horses.cpp: In function 'll getMul(int, int)':
horses.cpp:23:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   23 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |      ~~~^~~~
horses.cpp:23:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   23 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |                ~~~^~~~
horses.cpp: In function 'll getMax(int, int)':
horses.cpp:32:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   32 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |      ~~~^~~~
horses.cpp:32:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   32 |  for(ql += n , qr += n ; ql < qr ; ql >>= 1 , qr >>= 1){
      |                ~~~^~~~
horses.cpp: In function 'll solve()':
horses.cpp:44:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   44 |   ans = max(ans , getMax(cur , prv)) * x[cur];
      |                          ^~~
horses.cpp:44:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   44 |   ans = max(ans , getMax(cur , prv)) * x[cur];
      |                                ^~~
horses.cpp:48:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |  return ans % MOD * getMul(0 , cur) % MOD;
      |                                ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:62:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   62 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:69:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:75:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   75 |  return solve();
      |         ~~~~~^~
#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...