Submission #712327

#TimeUsernameProblemLanguageResultExecution timeMemory
712327Nhoksocqt1Horses (IOI15_horses)C++17
100 / 100
1461 ms40704 KiB
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define sz(x) int((x).size()) #define fi first #define se second typedef long long ll; typedef pair<int, int> ii; template<class X, class Y> inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);} template<class X, class Y> inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int Random(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } struct Bignum { static const int MAX_DIGIT = 5; static const int BASE = (int) 1e9; int digits[MAX_DIGIT], numDigit; Bignum(ll x = 0) { numDigit = 0; memset(digits, 0, sizeof digits); if (!x) numDigit = 1; while (x > 0) { digits[numDigit++] = x % BASE; x /= BASE; } } Bignum& operator += (const Bignum &x) { int carry(0); numDigit = max(numDigit, x.numDigit); for (int i = 0; i < numDigit; ++i) { digits[i] += x.digits[i] + carry; if (digits[i] >= BASE) { digits[i] -= BASE; carry = 1; } else { carry = 0; } } if (carry) digits[numDigit++] = carry; return *this; } Bignum operator + (const Bignum &x) const { Bignum res(*this); return res += x; } Bignum& operator *= (int x) { if (!x) { *this = Bignum(0); return *this; } ll remain = 0; for (int i = 0; i < numDigit; ++i) { remain += 1LL * digits[i] * x; digits[i] = remain % BASE; remain /= BASE; } while (remain > 0) { digits[numDigit++] = remain % BASE; remain /= BASE; } return *this; } Bignum operator * (int x) const { Bignum res(*this); res *= x; return res; } ll operator % (ll x) const { ll res(0); for (int i = numDigit - 1; i >= 0; i--) res = (res * BASE + digits[i]) % x; return res; } #define COMPARE(a, b) (((a) > (b)) - ((a) < (b))) int compare(const Bignum &x) const { if (numDigit != x.numDigit) { return COMPARE(numDigit, x.numDigit); } for (int i = numDigit - 1; i >= 0; --i) { if (digits[i] != x.digits[i]) { return COMPARE(digits[i], x.digits[i]); } } return 0; } #define DEF_OPER(o) bool operator o (const Bignum &x) const { return compare(x) o 0; } DEF_OPER(<) DEF_OPER(>) DEF_OPER(>=) DEF_OPER(<=) DEF_OPER(==) DEF_OPER(!=) #undef DEF_OPER }; const int MAXN = 500005; const int modl = 1e9+7; ll seg[4 * MAXN], seg1[4 * MAXN]; int X[MAXN], Y[MAXN], nArr; #ifdef Nhoksocqt1 int init(int _N, int _X[], int _Y[]); int updateX(int pos, int val); int updateY(int pos, int val); int _X[MAXN], _Y[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen("HORSES.inp", "r", stdin); freopen("HORSES.out", "w", stdout); int _N; cin >> _N; for (int i = 0; i < _N; ++i) { cin >> _X[i]; //_X[i] = Random(1, 1e9); cout << _X[i] << " \n"[i + 1 == _N]; } for (int i = 0; i < _N; ++i) { cin >> _Y[i]; //_Y[i] = Random(1, 1e9); cout << _Y[i] << " \n"[i + 1 == _N]; } cout << init(_N, _X, _Y) << '\n'; int Q; cin >> Q; while(Q--) { int type, pos, val; cin >> type >> pos >> val; type = Random(0, 1), pos = Random(0, _N - 1), val = Random(1, 1e9); cout << type << ' ' << pos << ' ' << val << '\n'; if(type == 0) { cout << updateX(pos, val) << '\n'; } else { cout << updateY(pos, val) << '\n'; } } return 0; } #endif // Nhoksocqt1 ll powermod(ll a, int exponent) { ll res(1); while(exponent > 0) { if(exponent & 1) res = res * a % modl; a = a * a % modl; exponent >>= 1; } return res; } int segx[4 * MAXN], segy[4 * MAXN]; void build(int seg[], int id, int l, int r, int x[]) { if(l == r) { seg[id] = x[l]; return; } int mid = (l + r) >> 1; build(seg, id << 1, l, mid, x); build(seg, id << 1 | 1, mid + 1, r, x); seg[id] = max(seg[id << 1], seg[id << 1 | 1]); } void update(int seg[], int pos, int val) { int id(1), l(1), r(nArr); while(l != r) { int mid = (l + r) >> 1; if(pos <= mid) { id = id << 1; r = mid; } else { id = id << 1 | 1; l = mid + 1; } } seg[id] = val; while(id > 1) { id >>= 1; seg[id] = max(seg[id << 1], seg[id << 1 | 1]); } } int findFirst(int seg[], int id, int l, int r, int pos, int k) { if(seg[id] < k || pos > r) return nArr + 1; if(pos <= l) { while(l != r) { int mid = (l + r) >> 1; if(seg[id << 1] < k) { id = id << 1 | 1; l = mid + 1; } else { id = id << 1; r = mid; } } return l; } int mid = (l + r) >> 1; return min(findFirst(seg, id << 1, l, mid, pos, k), findFirst(seg, id << 1 | 1, mid + 1, r, pos, k)); } void modify(int pos, int val) { int id(1), l(1), r(nArr); while(l != r) { int mid = (l + r) >> 1; if(pos <= mid) { id = id << 1; r = mid; } else { id = id << 1 | 1; l = mid + 1; } } seg[id] = val; while(id > 1) { id >>= 1; seg[id] = min(ll(1e9)+1, 1LL * seg[id << 1] * seg[id << 1 | 1]); } } int get(int k) { ll prod(1); int id(1), l(1), r(nArr); while(l != r) { int mid = (l + r) >> 1; if(prod * seg[id << 1 | 1] < k) { prod *= seg[id << 1 | 1]; id = id << 1; r = mid; } else { id = id << 1 | 1; l = mid + 1; } } return l; } void modify1(int pos, int val) { int id(1), l(1), r(nArr); while(l != r) { int mid = (l + r) >> 1; if(pos <= mid) { id = id << 1; r = mid; } else { id = id << 1 | 1; l = mid + 1; } } seg1[id] = val; while(id > 1) { id >>= 1; seg1[id] = 1LL * seg1[id << 1] * seg1[id << 1 | 1] % modl; } } int get1(int id, int l, int r, int u, int v) { if(v < l || u > r) return 1; if(u <= l && r <= v) return seg1[id]; int mid = (l + r) >> 1; return 1LL * get1(id << 1, l, mid, u, v) * get1(id << 1 | 1, mid + 1, r, u, v) % modl; } int calc2(void) { Bignum prodNow(1); int opt(nArr); while(opt > 0 && prodNow <= 1e9) { prodNow *= X[opt]; --opt; } while(opt > 0 && X[opt] == 1) --opt; ll res(1); Bignum ans(1); for (int i = 1; i <= opt; ++i) res = res * X[i] % modl; Bignum prod(1); while(opt <= nArr) { ans = max(ans, prod * Y[opt]); prod *= X[++opt]; } return res * (ans % modl) % modl; } int query(int seg[], int id, int l, int r, int u, int v) { if(v < l || u > r) return 0; if(u <= l && r <= v) return seg[id]; int mid = (l + r) >> 1; return max(query(seg, id << 1, l, mid, u, v), query(seg, id << 1 | 1, mid + 1, r, u, v)); } typedef pair<ll, ll> pll; int calc(void) { int opt = get(int(1e9)+1) - 1; int l = 1, r = opt; while(l <= r) { int mid = (l + r) >> 1; if(query(segx, 1, 1, nArr, mid, opt) == 1) { opt = mid; r = mid - 1; } else { l = mid + 1; } } pll ansNow = {0, 0}; ll res = (opt == 0) ? 1 : get1(1, 1, nArr, 1, opt), prod(1); while(opt <= nArr) { int nxt = findFirst(segx, 1, 1, nArr, opt + 1, 2); int maxY = query(segy, 1, 1, nArr, max(1, opt), nxt - 1); if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se) ansNow = {prod, maxY}; prod *= X[nxt]; opt = nxt; } ll ans = ansNow.fi % modl * ansNow.se % modl; return res * ans % modl; } int init(int _N, int _X[], int _Y[]) { nArr = _N; for (int i = 1; i <= nArr; ++i) { X[i] = _X[i - 1]; Y[i] = _Y[i - 1]; } build(segx, 1, 1, nArr, X); build(segy, 1, 1, nArr, Y); for (int i = 1; i <= nArr; ++i) modify(i, X[i]), modify1(i, X[i]); return calc(); } int updateX(int pos, int val) { ++pos; modify(pos, val); modify1(pos, val); update(segx, pos, val); X[pos] = val; return calc(); } int updateY(int pos, int val) { ++pos; Y[pos] = val; update(segy, pos, val); return calc(); }

Compilation message (stderr)

horses.cpp: In constructor 'Bignum::Bignum(ll)':
horses.cpp:34:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   34 |             digits[numDigit++] = x % BASE;
      |                                  ~~^~~~~~
horses.cpp: In member function 'Bignum& Bignum::operator*=(int)':
horses.cpp:74:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   74 |             digits[i] = remain % BASE;
      |                         ~~~~~~~^~~~~~
horses.cpp:79:41: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   79 |             digits[numDigit++] = remain % BASE;
      |                                  ~~~~~~~^~~~~~
horses.cpp: In function 'void build(int*, int, int, int, int*)':
horses.cpp:190:16: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  190 | void build(int seg[], int id, int l, int r, int x[]) {
      |            ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'void update(int*, int, int)':
horses.cpp:202:17: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  202 | void update(int seg[], int pos, int val) {
      |             ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int findFirst(int*, int, int, int, int, int)':
horses.cpp:222:19: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  222 | int findFirst(int seg[], int id, int l, int r, int pos, int k) {
      |               ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int get1(int, int, int, int, int)':
horses.cpp:308:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  308 |         return seg1[id];
      |                ~~~~~~~^
horses.cpp:311:84: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  311 |     return 1LL * get1(id << 1, l, mid, u, v) * get1(id << 1 | 1, mid + 1, r, u, v) % modl;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int calc2()':
horses.cpp:336:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  336 |     return res * (ans % modl) % modl;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp: In function 'int query(int*, int, int, int, int, int)':
horses.cpp:339:15: warning: declaration of 'seg' shadows a global declaration [-Wshadow]
  339 | int query(int seg[], int id, int l, int r, int u, int v) {
      |           ~~~~^~~~~
horses.cpp:122:4: note: shadowed declaration is here
  122 | ll seg[4 * MAXN], seg1[4 * MAXN];
      |    ^~~
horses.cpp: In function 'int calc()':
horses.cpp:8:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
    8 | #define se second
      |            ^
horses.cpp:370:75: note: in expansion of macro 'se'
  370 |         if(!ansNow.se || double(ansNow.fi) / maxY < double(prod) / ansNow.se)
      |                                                                           ^~
horses.cpp:378:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  378 |     return res * ans % modl;
      |            ~~~~~~~~~~^~~~~~
#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...