Submission #955701

#TimeUsernameProblemLanguageResultExecution timeMemory
955701emad234Horses (IOI15_horses)C++17
54 / 100
1574 ms63316 KiB
#include "horses.h" #include <bits/stdc++.h> #define ll long long #define F first #define S second #define pii pair<ll, ll> const ll mod = 1e9 + 7; const ll mxN = 5e5 + 5; using namespace std; ll NN; struct tree { vector<pii> seg; ll s, e; void init(ll n) { NN = exp2(ceil(log2(n))); seg.resize(NN * 4); } ll queryMax(ll l = 1, ll r = NN, ll ind = 1) { if (l > e || r < s) return 0; if (l >= s && r <= e) return seg[ind].F; ll md = (l + r) / 2; return max(queryMax(l, md, ind * 2), queryMax(md + 1, r, ind * 2 + 1)); } ll queryProd(ll l = 1, ll r = NN, ll ind = 1) { if (l > e || r < s) return 1; if (l >= s && r <= e) return seg[ind].S; ll md = (l + r) / 2; return (queryProd(l, md, ind * 2) * queryProd(md + 1, r, ind * 2 + 1)) % mod; } void update(pii val, ll ind) { ind += NN; seg[ind] = val; while (ind /= 2) { seg[ind].F = max(seg[ind * 2].F, seg[ind * 2 + 1].F); seg[ind].S = (seg[ind * 2].S * seg[ind * 2 + 1].S) % mod; } } } seg; struct ones { ll l, r; friend bool operator<(ones a, ones b) { return a.l < b.l; } }; set<ones> s; ll st[mxN],ed[mxN]; ll x[mxN], y[mxN]; ll vals[mxN]; ll n; ll solve() { ll id = 0; int i = n - 1; while (i > 0 && id <= 70) { if (x[i] == 1) { i = st[i]; id--; } i--; id++; } if(i == -1) i = 0; ll mx = -1, mxid = -1; ll prd = 1; for (i; i < n; i++) { if (x[i] == -1) { seg.s = i + 1, seg.e = ed[i] + 1; if (vals[i] * prd > mx) { mx = vals[i]; mxid = i; prd = 1; } i = ed[i]; continue; } if (prd * x[i] > mx) { mx = y[i]; mxid = i; prd = 1; continue; } prd *= x[i]; if (prd * y[i] > mx) { mx = y[i]; mxid = i; prd = 1; continue; } } seg.s = 1; seg.e = mxid + 1; return (mx * seg.queryProd()) % mod; } int init(int N, int X[], int Y[]) { seg.init(N); n = N; for (ll i = 0; i < N; i++) { y[i] = Y[i]; x[i] = X[i]; seg.update({Y[i], X[i]}, i); } ll l = -1, r = -1; for (ll i = 0; i < N; i++) { if (X[i] == 1) { if (l == -1) l = i; r = i; } else { if (l != -1) { s.insert({l, r}); l = r = -1; } } } if (l != -1) { s.insert({l, r}); l = r = -1; } return solve(); } int updateX(int pos, int val) { if (x[pos] != 1 && val == 1) { auto it = s.upper_bound({pos, pos}); ll l = pos, r = pos; if (it != s.end() && (*it).l == pos + 1) { l = pos, r = (*it).r; s.erase(it); } s.insert({l, r}); it = s.lower_bound({pos, pos}); auto p = s.lower_bound({l, r}); if (it != s.begin()) { it--; if ((*it).r == l - 1) { l = (*it).l; s.erase(it); s.erase(s.lower_bound({pos, pos})); s.insert({l, r}); } } st[r] = l; ed[l] = r; seg.s = l + 1,seg.e = r + 1; vals[l] = seg.queryMax(); } if (x[pos] == 1 && val != 1) { auto it = s.upper_bound({pos, 0}); it--; ll l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r; s.erase(it); if (l <= r){ s.insert({l, r}); st[r] = l; ed[l] = r; seg.s = l + 1, seg.e = r + 1; vals[l] = seg.queryMax(); } if (l1 <= r1){ s.insert({l1, r1}); st[r1] = l1; ed[l1] = r1; seg.s = l1 + 1, seg.e = r1 + 1; vals[l1] = seg.queryMax(); } } x[pos] = val; seg.update({y[pos], x[pos]}, pos); return solve(); } int updateY(int pos, int val) { y[pos] = val; seg.update({y[pos], x[pos]}, pos); return solve(); }

Compilation message (stderr)

horses.cpp: In member function 'void tree::init(long long int)':
horses.cpp:18:12: warning: conversion from 'double' to 'long long int' may change value [-Wfloat-conversion]
   18 |   NN = exp2(ceil(log2(n)));
      |        ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:66:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   66 |  int i = n - 1;
      |          ~~^~~
horses.cpp:71:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |    i = st[i];
      |        ~~~~^
horses.cpp:80:7: warning: statement has no effect [-Wunused-value]
   80 |  for (i; i < n; i++)
      |       ^
horses.cpp:91:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |    i = ed[i];
      |        ~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:147:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:163:8: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  163 |   auto p = s.lower_bound({l, r});
      |        ^
horses.cpp:203:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  203 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:210:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  210 |  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...