Submission #955672

#TimeUsernameProblemLanguageResultExecution timeMemory
955672emad234Horses (IOI15_horses)C++17
20 / 100
171 ms45924 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; int NN; struct tree { vector<pii> seg; ll s, e; void init(int n) { NN = exp2(ceil(log2(n))); seg.resize(NN * 4); } ll queryMax(int l = 1, int r = NN, int ind = 1) { if (l > e || r < s) return 0; if (l >= s && r <= e) return seg[ind].F; int md = (l + r) / 2; return max(queryMax(l, md, ind * 2), queryMax(md + 1, r, ind * 2 + 1)); } ll queryProd(int l = 1, int r = NN, int ind = 1) { if (l > e || r < s) return 1; if (l >= s && r <= e) return seg[ind].S; int md = (l + r) / 2; return (queryProd(l, md, ind * 2) * queryProd(md + 1, r, ind * 2 + 1)) % mod; } void update(pii val, int 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 x[mxN], y[mxN]; int n; ll solve() { int st, id = 0; int i = n - 1; while (i && id <= 100) { if (x[i] == 1) { auto it = s.upper_bound({i, i}); it--; i = (*it).l; } i--; id++; } ll mx = -1, mxid = -1; ll prd = 1; for (i; i < n; i++) { if (x[i] == 1) { auto it = s.lower_bound({i, i}); seg.s = (*it).l + 1, seg.e = (*it).r + 1; ll val = seg.queryMax(); if (val * prd > mx) { mx = val; mxid = i; prd = 1; } i = (*it).r; 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 (int i = 0; i < N; i++) { y[i] = Y[i]; x[i] = X[i]; seg.update({Y[i], X[i]}, i); } int l = -1, r = -1; for (int 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}); int l = pos, r = pos; if (it != s.end() && (*it).l == pos + 1) { l = pos, r = (*it).r; s.erase(it); s.insert({l, r}); } else s.insert({pos, pos}); 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}); } } } if (x[pos] == 1 && val != 1) { auto it = s.upper_bound({pos, 0}); it--; int l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r; s.erase(it); if (l <= r) s.insert({l, r}); if (l1 <= r1) s.insert({l1, r1}); } 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(int)':
horses.cpp:18:12: warning: conversion from 'double' to 'int' may change value [-Wfloat-conversion]
   18 |   NN = exp2(ceil(log2(n)));
      |        ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:71:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |    i = (*it).l;
      |        ~~~~~~^
horses.cpp:78:7: warning: statement has no effect [-Wunused-value]
   78 |  for (i; i < n; i++)
      |       ^
horses.cpp:91:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |    i = (*it).r;
      |        ~~~~~~^
horses.cpp:63:6: warning: unused variable 'st' [-Wunused-variable]
   63 |  int st, id = 0;
      |      ^~
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:158:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 |    l = pos, r = (*it).r;
      |                 ~~~~~~^
horses.cpp:171:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  171 |     l = (*it).l;
      |         ~~~~~~^
horses.cpp:165:8: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  165 |   auto p = s.lower_bound({l, r});
      |        ^
horses.cpp:182:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  182 |   int l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r;
      |           ~~~~~~^
horses.cpp:182:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  182 |   int l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r;
      |                                                    ~~~~~~^
horses.cpp:191:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  191 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:198:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  198 |  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...