Submission #390644

#TimeUsernameProblemLanguageResultExecution timeMemory
390644WLZHorses (IOI15_horses)C++14
100 / 100
1112 ms92100 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; const int MOD = (int) 1e9 + 7; int add(int a, int b) { if (a + b >= MOD) return a + b - MOD; return a + b; } int mul(int a, int b) { return (long long) a * b % MOD; } int n; vector<int> x, y; set<int> st; struct node { int l, r, mx, pr; node *left, *right; } *root; node *build(int l, int r) { if (l == r) return new node{l, r, y[l], x[l], nullptr, nullptr}; node *left = build(l, (l + r) / 2); node *right = build((l + r) / 2 + 1, r); return new node{l, r, max(left->mx, right->mx), mul(left->pr, right->pr), left, right}; } void update(node *cur, int pos) { if (cur->l == cur->r) { cur->mx = y[pos], cur->pr = x[pos]; return; } if (pos <= cur->left->r) update(cur->left, pos); else update(cur->right, pos); cur->mx = max(cur->left->mx, cur->right->mx); cur->pr = mul(cur->left->pr, cur->right->pr); } int query_mx(node *cur, int l, int r) { if (cur->l > r || cur->r < l) return 0; if (l <= cur->l && cur->r <= r) return cur->mx; return max(query_mx(cur->left, l, r), query_mx(cur->right, l, r)); } int query_pr(node *cur, int l, int r) { if (cur->l > r || cur->r < l) return 1; if (l <= cur->l && cur->r <= r) return cur->pr; return mul(query_pr(cur->left, l, r), query_pr(cur->right, l, r)); } int calc_ans() { int i = 0; st.insert(0); vector<int> v; for (auto it = st.rbegin(); it != st.rend() && i < 30; it++, i++) { v.push_back(*it); } reverse(v.begin(), v.end()); int best = 0; long long cur = 1, mx = query_mx(root, v[0], (int) v.size() > 1 ? v[1] - 1 : n - 1); for (i = 1; i < (int) v.size(); i++) { long long tmp = query_mx(root, v[i], i < (int) v.size() - 1 ? v[i + 1] - 1 : n - 1); if (cur * x[v[i]] > mx) { cur = 1, mx = tmp, best = i; continue; } cur *= x[v[i]]; if (cur * tmp > mx) { cur = 1, mx = tmp, best = i; } } return mul(query_pr(root, 0, v[best]), query_mx(root, v[best], best < (int) v.size() - 1 ? v[best + 1] - 1 : n - 1)); } int init(int N, int X[], int Y[]) { n = N; x.assign(X, X + n); y.assign(Y, Y + n); for (int i = 0; i < n; i++) if (x[i] != 1) st.insert(i); root = build(0, n - 1); return calc_ans(); } int updateX(int pos, int val) { if (x[pos] != val) { if (val != 1) st.insert(pos); else if (st.count(pos)) st.erase(pos); x[pos] = val; update(root, pos); } return calc_ans(); } int updateY(int pos, int val) { y[pos] = val; update(root, pos); return calc_ans(); }

Compilation message (stderr)

horses.cpp: In function 'int mul(int, int)':
horses.cpp:13:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   13 |   return (long long) a * b % MOD;
      |          ~~~~~~~~~~~~~~~~~~^~~~~
#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...