Submission #785191

#TimeUsernameProblemLanguageResultExecution timeMemory
785191fatemetmhrHorses (IOI15_horses)C++17
37 / 100
471 ms38664 KiB
// ~ Be Name Khoda ~ // #include "horses.h" #include <bits/stdc++.h> //#pragma GCC optimize ("O3") //#pragma GCC target("avx2") //#pragma GCC optimize("unroll-loops,Ofast") using namespace std; typedef long long ll; #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define fi first #define se second const int maxn = 1e6 + 10; const int maxn5 = 5e5 + 10; const int maxnt = 1.2e6 + 10; const int maxn3 = 1e3 + 10; const int mod = 1e9 + 7; const ll inf = 1e18; int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5]; set <int> av; ll all = 1; ll pw(ll a, ll b){ ll ret = 1; for(; b; b >>= 1, a = a * a % mod) if(b & 1) ret = ret * a % mod; return ret; } void build(int l, int r, int v){ if(r - l == 1){ mx[v] = val[l]; return; } int mid = (l + r) >> 1; build(l, mid, v * 2); build(mid, r, v * 2 + 1); mx[v] = max(mx[v * 2], mx[v * 2 + 1]); } void update(int l, int r, int id, int val, int v){ if(r - l == 1){ mx[v] = val; return; } int mid = (l + r) >> 1; if(id < mid) update(l, mid, id, val, v * 2); else update(mid, r, id, val, v * 2 + 1); mx[v] = max(mx[v * 2], mx[v * 2 + 1]); return; } int get_max(int l, int r, int lq, int rq, int v){ if(rq <= l || r <= lq) return 0; if(lq <= l && r <= rq) return mx[v]; int mid = (l + r) >> 1; return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1)); } ll get_ans(){ //cout << av.size() << endl; if(av.empty()) return mx[1]; auto it = av.end(); it--; ll mx = 0; ll rem = all; //cout << "ha " << all << endl; while(true){ int id = *it; ll have = get_max(0, n, id, n, 1); mx = max(mx, have); mx = mx * rat[id]; rem = rem * rev[id] % mod; //cout << "we had " << mx << ' ' << rem << endl; if(it == av.begin()){ mx = max(mx, ll(::mx[1])); return mx; } if(mx >= mod) break; it--; } return (mx % mod) * rem % mod; } int init(int N, int X[], int Y[]){ n = N; for(int i = 0; i < n; i++){ rat[i] = X[i]; val[i] = Y[i]; all = all * rat[i] % mod; rev[i] = pw(rat[i], mod - 2); if(rat[i] > 1) av.insert(i); //cout << i << ' ' << rat[i] << ' ' << av.size() << endl; } build(0, n, 1); return get_ans(); } int updateX(int pos, int val){ all = all * rev[pos] % mod; rev[pos] = pw(val, mod - 2); all = all * val % mod; if(rat[pos] > 1) av.erase(pos); rat[pos] = val; if(val > 1) av.insert(pos); return get_ans(); } int updateY(int pos, int val) { //cout << "here " << pos << ' ' << val << endl; update(0, n, pos, val, 1); return get_ans(); }

Compilation message (stderr)

horses.cpp: In function 'void update(int, int, int, int, int)':
horses.cpp:48:39: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   48 | void update(int l, int r, int id, int val, int v){
      |                                   ~~~~^~~
horses.cpp:26:19: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |                   ^~~
horses.cpp: In function 'll get_ans()':
horses.cpp:76:5: warning: declaration of 'mx' shadows a global declaration [-Wshadow]
   76 |  ll mx = 0;
      |     ^~
horses.cpp:26:8: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |        ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:105:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  105 |   rev[i] = pw(rat[i], mod - 2);
      |            ~~^~~~~~~~~~~~~~~~~
horses.cpp:112:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:115:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  115 | int updateX(int pos, int val){
      |                      ~~~~^~~
horses.cpp:26:19: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |                   ^~~
horses.cpp:117:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |  rev[pos] = pw(val, mod - 2);
      |             ~~^~~~~~~~~~~~~~
horses.cpp:124:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  124 |  return get_ans();
      |         ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:127:26: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  127 | int updateY(int pos, int val) {
      |                      ~~~~^~~
horses.cpp:26:19: note: shadowed declaration is here
   26 | int n, mx[maxnt], val[maxn5], rat[maxn5], rev[maxn5];
      |                   ^~~
horses.cpp:130:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |  return get_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...