제출 #212232

#제출 시각아이디문제언어결과실행 시간메모리
212232apostoldaniel854말 (IOI15_horses)C++14
0 / 100
647 ms61304 KiB
#include <horses.h> #include <bits/stdc++.h> using namespace std; struct RangeSeg { int startRange; int endRange; int bestY; bool operator < (RangeSeg const &other) const { return startRange < other.startRange; } }; set <RangeSeg> Intervals; const int MOD = 1e9 + 7, MAX_N = 5e5; int N; int X[1 + MAX_N]; int Y[1 + MAX_N]; struct Bit { vector <int> aib; int n; int lsb (int x) { return x & -x; } void init (int _n) { n = _n; aib.resize (n + 1, 1); } void upd (int pos, int val) { while (pos <= n) { aib[pos] = (1ll * aib[pos] * val) % MOD; pos += lsb (pos); } } int qry (int pos) { int ans = 1; while (pos) { ans = (1ll * ans * aib[pos]) % MOD; pos -= lsb (pos); } return ans; } }; struct SegMax { vector <int> seg; int n; int query (int node, int l, int r, int nl, int nr) { if (nl <= l && r <= nr) return seg[node]; int mid = (l + r) / 2; int ans = 0; if (mid >= nl) ans = max (ans, query (2 * node, l, mid, nl, nr)); if (mid < nr) ans = max (ans, query (2 * node + 1, mid + 1, r, nl, nr)); return ans; } void update (int node, int l, int r, int pos, int val) { if (l == r) { seg[node] = val; return; } int mid = (l + r) / 2; if (mid >= pos) update (2 * node, l, mid, pos, val); else update (2 * node + 1, mid + 1, r, pos, val); seg[node] = max (seg[2 * node], seg[2 * node + 1]); } void init (int _n) { n = _n; seg.resize (4 * n + 1, 0); } void updateVal (int pos, int val) { update (1, 1, n, pos, val); } int queryRange (int l, int r) { return query (1, 1, n, l, r); } }; SegMax MaxY; Bit aibMOD; const int MAGIC = 30; typedef long double ld; ld Total; const ld EPS = 1e-12; int getAns () { int NoSeg = 0; auto it = Intervals.end (); it = prev (it); ld xTot = Total; ld best = -1; int bestMOD = 0; while (NoSeg < min (MAGIC, (int) Intervals.size ())) { RangeSeg x = *it; xTot -= log2 (X[x.startRange]); if (log2 (x.bestY) + xTot - best > EPS) { best = log2 (x.bestY) + xTot; bestMOD = 1ll * aibMOD.qry (x.startRange) * x.bestY % MOD; } it = prev (it); NoSeg++; } return bestMOD; } int lgput (int a, int b) { int ans = 1; while (b) { if (b & 1) ans = 1ll * ans * a % MOD; a = 1ll * a * a % MOD; b /= 2; } return ans; } int inv (int x) { return lgput (x, MOD - 2); } void split (set <RangeSeg>::iterator it, int pos) { RangeSeg x = *it; if (pos == x.startRange) return; Intervals.erase (it); RangeSeg x1 = {x.startRange, pos - 1, MaxY.queryRange (x.startRange, pos - 1)}, x2 = {pos, x.endRange, MaxY.queryRange (pos, x.endRange)}; Intervals.insert (x1); Intervals.insert (x2); } void join (set <RangeSeg>::iterator it1, set <RangeSeg>::iterator it2) { RangeSeg x1 = *it1, x2 = *it2; Intervals.erase (it1); Intervals.erase (it2); RangeSeg x = {x1.startRange, x2.endRange, MaxY.queryRange (x1.startRange, x2.endRange)}; Intervals.insert (x); } int updateX (int pos, int val) { aibMOD.upd (pos, inv (X[pos])); aibMOD.upd (pos, val); if (val == 1) { if (X[pos] != 1) { set <RangeSeg>::iterator it2 = Intervals.lower_bound ({pos, 0, 0}); if (it2 != Intervals.begin ()) { set <RangeSeg>::iterator it1 = prev (it2); join (it1, it2); } } } else { if (X[pos] == 1) { set <RangeSeg>::iterator it = Intervals.lower_bound ({pos + 1, 0, 0}); it = prev (it); split (it, pos); } } X[pos] = val; return getAns (); } int updateY (int pos, int val) { MaxY.updateVal (pos, val); set <RangeSeg>::iterator it = Intervals.lower_bound ({pos + 1, 0, 0}); it = prev (it); /// why??? auto x = *it; Intervals.erase (it); x.bestY = MaxY.queryRange (x.startRange, x.endRange); Intervals.insert (x); return getAns (); } int init (int n, int x[], int y[]) { N = n; for (int i = 1; i <= N; i++) X[i] = x[i], Y[i] = y[i]; MaxY.init (N); for (int i = 1; i <= N; i++) MaxY.updateVal (i, Y[i]); aibMOD.init (N); int startIndex = 1; for (int i = 1; i <= N; i++) { Total += log (X[i]); aibMOD.upd (i, X[i]); if (X[i] > 1) { if (i > 1) Intervals.insert ({startIndex, i - 1, MaxY.queryRange (startIndex, i - 1)}); startIndex = i; } } Intervals.insert ({startIndex, n, MaxY.queryRange (startIndex, n)}); for (auto x : Intervals) { cout << x.startRange << " " << x.endRange << " " << x.bestY << "\n"; } return getAns (); } /** 5 1 2 1 1 2 2 3 4 5 6 3 2 3 20 1 2 1 2 3 1 **/ /*int x[1 + MAX_N], y[1 + MAX_N]; int main () { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> x[i]; for (int i = 1; i <= n; i++) cin >> y[i]; cout << init (n, x, y) << "\n"; int m; cin >> m; for (int i = 1; i <= m; i++) { int pos, val, type; cin >> type >> pos >> val; if (type == 1) cout << updateX (pos, val) << "\n"; else cout << updateY (pos, val) << "\n"; } return 0; }*/

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

horses.cpp: In member function 'void Bit::upd(int, int)':
horses.cpp:40:47: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
             aib[pos] = (1ll * aib[pos] * val) % MOD;
                        ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int Bit::qry(int)':
horses.cpp:47:42: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             ans = (1ll * ans * aib[pos]) % MOD;
                   ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getAns()':
horses.cpp:115:65: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             bestMOD = 1ll * aibMOD.qry (x.startRange) * x.bestY % MOD;
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int lgput(int, int)':
horses.cpp:131:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             ans = 1ll * ans * a % MOD;
                   ~~~~~~~~~~~~~~^~~~~
horses.cpp:132:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         a = 1ll * a * a % MOD;
             ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:218:15: warning: declaration of 'auto x' shadows a parameter [-Wshadow]
     for (auto x : Intervals) {
               ^
horses.cpp:196:24: note: shadowed declaration is here
 int init (int n, int x[], int y[]) {
                        ^
#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...