제출 #299144

#제출 시각아이디문제언어결과실행 시간메모리
299144Haunted_Cpp말 (IOI15_horses)C++17
34 / 100
1560 ms95916 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 5e5 + 5; const int MAX_K = 30 + 5; const int MOD = 1e9 + 7; int _N; vector<int> _X(MAX_N), _Y(MAX_N); set<int> non_one; int mult(int a, int b) { long long res = 1LL * a * b; if (res >= MOD) res %= MOD; return res; } class SegmentTree { private: struct Node { int product; int opt; Node() { product = 1; opt = -1; } void merge(Node l, Node r, int rightmost) { product = mult(l.product, r.product); opt = l.opt; assert ( (l.opt == -1 && r.opt == -1) == false ); if (l.opt == -1) { opt = r.opt; return; } if (r.opt == -1) { opt = l.opt; return; } auto start_location = non_one.upper_bound(opt); long long best_multiplier = _Y[opt]; long long road = 1; for (int i = 0; i < MAX_K && start_location != non_one.end() && *start_location <= rightmost; i++) { int cur = _X[*start_location]; long long nxt = 1LL * road * cur; if (nxt >= best_multiplier || (nxt * _Y[*start_location] >= best_multiplier)) { opt = r.opt; break; } start_location = next(start_location); road = nxt; } if (1LL * road * _Y[r.opt] >= best_multiplier) { opt = r.opt; } } }; const int LO, HI; vector<Node> seg; void update(int where, int delta, int l, int r, int node) { if (l > where || r < where) { return; } if (l >= where && r <= where) { seg[node].opt = l; seg[node].product = delta; return; } const int mid = l + (r - l) / 2; update(where, delta, l, mid, 2 * node + 1); update(where, delta, mid + 1, r, 2 * node + 2); seg[node].merge(seg[2 * node + 1], seg[2 * node + 2], r); } int query(int ql, int qr, int l, int r, int node) { if (l > qr || r < ql) { return 1; } if (l >= ql && r <= qr) { return seg[node].product; } const int mid = l + (r - l) / 2; return mult(query(ql, qr, l, mid, 2 * node + 1), query(ql, qr, mid + 1, r, 2 * node + 2)); } public: SegmentTree(int n) : LO(0), HI(n - 1) { seg = vector<Node>(4 * n); } void update(int where, int delta) { update(where, delta, LO, HI, 0); } int solve() { const int optimal_location = seg[0].opt; return mult( query(0, optimal_location, LO, HI, 0), _Y[optimal_location] ); } }; SegmentTree seg(4 * MAX_N); int init(int N, int X[], int Y[]) { for (int i = 0; i < N; i++) { _X[i] = X[i]; _Y[i] = Y[i]; if (_X[i] > 1) { non_one.insert(i); } } for (int i = 0; i < N; i++) { seg.update(i, _X[i]); } return seg.solve(); } int updateX(int pos, int val) { if (non_one.find(pos) != non_one.end()) { non_one.erase(pos); } _X[pos] = val; if (_X[pos] > 1) { non_one.insert(pos); } seg.update(pos, val); return seg.solve(); } int updateY(int pos, int val) { _Y[pos] = val; seg.update(pos, _X[pos]); return seg.solve(); }

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int mult(int, int)':
horses.cpp:16:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |   return res;
      |          ^~~
#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...