제출 #252038

#제출 시각아이디문제언어결과실행 시간메모리
252038DS007말 (IOI15_horses)C++14
17 / 100
1275 ms52984 KiB
#include <bits/stdc++.h> using namespace std; const long long N = 5e5, mod = 1e9 + 7; int n, *x, *y; set<int> s; class SegmentTree1 { int t[N * 4]; public: SegmentTree1() { fill(t, t + N * 4, 0); } void update(int v, int l, int r, int tl, int k) { if (l == r && l == tl) { t[v] = k; return; } int mid = (l + r) / 2; if (tl <= mid) update(v * 2, l, mid, tl, k); else update(v * 2 + 1, mid + 1, r, tl, k); t[v] = max(t[v * 2], t[v * 2 + 1]); } long long query(int v, int l, int r, int tl, int tr) { if (tl > tr) return -1; else if (l == tl && r == tr) return t[v]; int mid = (l + r) / 2; return max(query(v * 2, l, mid, tl, min(mid, tr)), query(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr)); } }; class SegmentTree2 { long long t[N * 4]; public: SegmentTree2() { fill(t, t + N * 4, 1); } void update(int v, int l, int r, int tl, int k) { if (l == r && l == tl) { t[v] = k; return; } int mid = (l + r) / 2; if (tl <= mid) update(v * 2, l, mid, tl, k); else update(v * 2 + 1, mid + 1, r, tl, k); t[v] = t[v * 2] * t[v * 2 + 1] % mod; } long long query(int v, int l, int r, int tl, int tr) { if (tl > tr) return 1; else if (l == tl && r == tr) return t[v]; int mid = (l + r) / 2; return query(v * 2, l, mid, tl, min(mid, tr)) * query(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr) % mod; } }; SegmentTree1 st1; SegmentTree2 st2; int query() { auto itr = s.rbegin(); long long temp = 1; vector<int> v; while (itr != s.rend() && temp < mod) { temp *= x[*itr]; assert(x[*itr] >= 2); v.push_back(*itr); itr++; } //for (int i : v) // cerr << i << " "; //cerr << endl; assert(v.size() <= 32); long long ans = 1; for (int i = 0; i < v.size(); i++) { long long cv = st2.query(1, 0, n - 1, v.back() + 1, v[i]); assert(cv < mod); ans = max(ans, cv * st1.query(1, 0, n - 1, v[i], n - 1)); //cerr << cv << " " << ans << endl; } ans = st2.query(1, 0, n - 1, 0, v.empty() ? 0 : v.back()) * ans; ans = max(ans, st1.query(1, 0, n - 1, 0, n - 1)); return int(ans % mod); } int init(int N, int X[], int Y[]) { n = N; x = X; y = Y; for (int i = 0; i < n; i++) { st2.update(1, 0, n - 1, i, x[i]); if (x[i] > 1) s.insert(i); st1.update(1, 0, n - 1, i, y[i]); } return query(); } int updateX(int pos, int val) { s.erase(pos); st2.update(1, 0, n - 1, pos, val); x[pos] = val; if (val > 1) s.insert(pos); return query(); } int updateY(int pos, int val) { y[pos] = val; st1.update(1, 0, n - 1, pos, val); return query(); }

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

horses.cpp: In function 'int query()':
horses.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:109:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:4:17: note: shadowed declaration is here
 const long long N = 5e5, mod = 1e9 + 7;
                 ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:128:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (val > 1)
     ^~
horses.cpp:130:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  return query();
  ^~~~~~
#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...