Submission #219607

#TimeUsernameProblemLanguageResultExecution timeMemory
219607summitweiHorses (IOI15_horses)C++17
100 / 100
1010 ms65692 KiB
#include <bits/stdc++.h> #include <horses.h> using namespace std; typedef vector<int> vi; typedef vector<pair<int, int> > vpii; typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef vector<ll> vll; #define INF 0x3f3f3f3f #define MOD 1000000007LL #define EPSILON 0.00001 #define f first #define s second #define pb push_back #define mp make_pair #define FOR(i, a, b) for (ll i=(a); i<=(signed)(b); i++) #define F0R(i, a) for (ll i=0; i<(signed)(a); i++) #define RFOR(i, a, b) for (ll i=(a); i >= b; i--) #define MN 500005 int n; ll a[MN]; ll b[MN]; ll tree[2][4*MN]; void upd(int node, int a, int b, int i, ll val, int tp){ if(a > i || b < i) return; if(a == b){ tree[tp][node] = val; return; } int mid = (a+b)/2; upd(node*2, a, mid, i, val, tp); upd(node*2+1, 1+mid, b, i, val, tp); if(tp == 0) tree[tp][node] = max(tree[tp][node*2], tree[tp][node*2+1]); else tree[tp][node] = (tree[tp][node*2]*tree[tp][node*2+1])%MOD; } ll que(int node, int a, int b, int i, int j, int tp){ if(a > j || b < i || j < i) return 1; if(i <= a && b <= j) return tree[tp][node]; int mid = (a+b)/2; ll q1 = que(node*2, a, mid, i, j, tp); ll q2 = que(node*2+1, 1+mid, b, i, j, tp); if(tp == 0) return max(q1, q2); else return (q1*q2)%MOD; } set<int, greater<int> > hmm; ll calc(){ hmm.insert(1); //1 as 1 might be relevant ll res = 0; int pv = n+1; for(auto cur : hmm){ //cout << "checking " << cur << " " << pv-1 << " range\n"; res = max(res, que(1, 1, n, cur, pv-1, 0)); res = res*a[cur]; //cout << "res now " << res << "\n"; if(res > MOD){ res %= MOD; ll ot = que(1, 1, n, 1, cur-1, 1); return (res*ot)%MOD; } pv = cur; } return res; } int init(int N, int x[], int y[]){ n = N; F0R(i, n){ upd(1, 1, n, i+1, x[i], 1); upd(1, 1, n, i+1, y[i], 0); if(x[i] != 1) hmm.insert(i+1); a[i+1] = x[i]; b[i+1] = y[i]; } return (int)calc(); } int updateX(int pos, int val){ ++pos; if(a[pos] == 1 && val != 1) hmm.insert(pos); else if(a[pos] != 1 && val == 1) hmm.erase(pos); a[pos] = val; upd(1, 1, n, pos, val, 1); return (int)calc(); } int updateY(int pos, int val){ ++pos; b[pos] = val; upd(1, 1, n, pos, val, 0); return (int)calc(); } /*int main(){ //ios_base::sync_with_stdio(false); //cin.tie(0); int n, m; cin >> n; int x[n], y[n]; F0R(i, n) cin >> x[i]; F0R(i, n) cin >> y[i]; cout << init(n, x, y) << "\n"; cin >> m; F0R(i, m){ int c, pos, val; cin >> c >> pos >> val; if(c == 0){ cout << updateX(pos, val) << "\n"; } else{ cout << updateY(pos, val) << "\n"; } } return 0; }*/

Compilation message (stderr)

horses.cpp: In function 'void upd(int, int, int, int, ll, int)':
horses.cpp:29:55: warning: declaration of 'b' shadows a global declaration [-Wshadow]
 void upd(int node, int a, int b, int i, ll val, int tp){
                                                       ^
horses.cpp:26:4: note: shadowed declaration is here
 ll b[MN];
    ^
horses.cpp:29:55: warning: declaration of 'a' shadows a global declaration [-Wshadow]
 void upd(int node, int a, int b, int i, ll val, int tp){
                                                       ^
horses.cpp:25:4: note: shadowed declaration is here
 ll a[MN];
    ^
horses.cpp: In function 'll que(int, int, int, int, int, int)':
horses.cpp:41:52: warning: declaration of 'b' shadows a global declaration [-Wshadow]
 ll que(int node, int a, int b, int i, int j, int tp){
                                                    ^
horses.cpp:26:4: note: shadowed declaration is here
 ll b[MN];
    ^
horses.cpp:41:52: warning: declaration of 'a' shadows a global declaration [-Wshadow]
 ll que(int node, int a, int b, int i, int j, int tp){
                                                    ^
horses.cpp:25:4: note: shadowed declaration is here
 ll a[MN];
    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:76:23: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         upd(1, 1, n, i+1, x[i], 1);
                      ~^~
horses.cpp:77:23: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
         upd(1, 1, n, i+1, y[i], 0);
                      ~^~
horses.cpp:78:35: warning: conversion to 'std::set<int, std::greater<int> >::value_type {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
         if(x[i] != 1) hmm.insert(i+1);
                                  ~^~
#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...