제출 #852982

#제출 시각아이디문제언어결과실행 시간메모리
852982aykhn말 (IOI15_horses)C++14
100 / 100
960 ms83496 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define ins insert #define infll 0x3F3F3F3F3F3F3F3F #define inf 0x3F3F3F3F #define pii pair<int, int> #define pll pair<ll, ll> #define mpr make_pair #define all(v) v.begin(), v.end() #define fi first #define se second const ll mod = 1e9 + 7; int n; vector<ll> a, b; set<ll> s; multiset<ll> ms; ll mult(ll a, ll b) { return (a * b) % mod; } struct SegTree { int sz; vector<ll> st; void build(int l, int r, int x) { if (l + 1 == r) { if (l < n) st[x] = mult(st[x], a[l]); return; } int mid = (l + r) >> 1; build(l, mid, 2*x + 1); build(mid, r, 2*x + 2); st[x] = mult(st[2*x + 1], st[2*x + 2]); } void build(int n) { sz = 1; while (sz < n) sz <<= 1; st.assign(sz << 1, 1); build(0, sz, 0); } void make(int ind, ll val, int l, int r, int x) { if (l + 1 == r) { st[x] = val; return; } int mid = (l + r) >> 1; if (ind < mid) make(ind, val, l, mid, 2*x + 1); else make(ind, val, mid, r, 2*x + 2); st[x] = mult(st[2*x + 1], st[2*x + 2]); } void make(int ind, ll val) { make(ind, val, 0, sz, 0); } ll get(int lx, int rx, int l, int r, int x) { if (l >= rx || r <= lx) return 1; if (l >= lx && r <= rx) return st[x]; int mid = (l + r) >> 1; return mult(get(lx, rx, l, mid, 2*x + 1), get(lx, rx, mid, r, 2*x + 2)); } ll get(int l, int r) { return get(l, r + 1, 0, sz, 0); } }; struct SegTreeMX { int sz; vector<ll> st; void build(int l, int r, int x) { if (l + 1 == r) { if (l < n) st[x] = b[l]; return; } int mid = (l + r) >> 1; build(l, mid, 2*x + 1); build(mid, r, 2*x + 2); st[x] = max(st[2*x + 1], st[2*x + 2]); } void build(int n) { sz = 1; while (sz < n) sz <<= 1; st.assign(sz << 1, 1); build(0, sz, 0); } void make(int ind, ll val, int l, int r, int x) { if (l + 1 == r) { st[x] = val; return; } int mid = (l + r) >> 1; if (ind < mid) make(ind, val, l, mid, 2*x + 1); else make(ind, val, mid, r, 2*x + 2); st[x] = max(st[2*x + 1], st[2*x + 2]); } void make(int ind, ll val) { make(ind, val, 0, sz, 0); } ll get(int lx, int rx, int l, int r, int x) { if (l >= rx || r <= lx) return 1; if (l >= lx && r <= rx) return st[x]; int mid = (l + r) >> 1; return max(get(lx, rx, l, mid, 2*x + 1), get(lx, rx, mid, r, 2*x + 2)); } ll get(int l, int r) { return get(l, r + 1, 0, sz, 0); } }; SegTree st; SegTreeMX stmx; ll getans() { ll ans = *ms.rbegin(); if (s.empty()) return ans; vector<int> v; int k = 1; for (auto it = s.rbegin(); k <= 30 && it != s.rend(); it++, k++) v.pb(*it); reverse(all(v)); ll mxb = stmx.get(v[0], (1 == v.size() ? n - 1 : v[1] - 1)); ll x = 1; ll INF = 1e18; int f = 0; int ind = 0; for (int i = 1; i < v.size(); i++) { if (a[v[i]] >= INF/x) f = 1; if (!f) x *= a[v[i]]; ll bb = stmx.get(v[i], (i + 1 == v.size() ? n - 1 : v[i + 1] - 1)); if (!f && x >= INF/bb) f = 1; if (!f) x *= bb; if (f || x > mxb) { ind = i; mxb = bb; f = 0; x = 1; } else x /= bb; } int szs = s.size(); int szv = v.size(); if (szs - (szv - ind) >= 30) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1))); f = 0; x = 1; for (auto it = s.begin(); it != s.end() && *it <= v[ind]; it++) { if (a[*it] >= INF/x) f = 1; if (!f) x *= a[*it]; } ll bb = stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)); if (bb >= INF/x) f = 1; if (!f) x *= bb; if (f || x > ans) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1))); else return ans; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < N; i++) { a.pb(X[i]), b.pb(Y[i]); if (X[i] > 1) s.ins(i); ms.ins(Y[i]); } st.build(n); stmx.build(n); return getans(); } int updateX(int pos, int val) { if (a[pos] > 1) s.erase(pos); a[pos] = val; if (a[pos] > 1) s.ins(pos); st.make(pos, val); return getans(); } int updateY(int pos, int val) { ms.erase(ms.lower_bound(b[pos])); ms.ins(val); b[pos] = val; stmx.make(pos, val); return getans(); }

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

horses.cpp: In function 'll mult(ll, ll)':
horses.cpp:25:18: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   25 | ll mult(ll a, ll b)
      |               ~~~^
horses.cpp:21:15: note: shadowed declaration is here
   21 | vector<ll> a, b;
      |               ^
horses.cpp:25:12: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   25 | ll mult(ll a, ll b)
      |         ~~~^
horses.cpp:21:12: note: shadowed declaration is here
   21 | vector<ll> a, b;
      |            ^
horses.cpp: In member function 'void SegTree::build(int)':
horses.cpp:46:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   46 |  void build(int n)
      |             ~~~~^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int n;
      |     ^
horses.cpp: In member function 'void SegTreeMX::build(int)':
horses.cpp:97:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   97 |  void build(int n)
      |             ~~~~^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int n;
      |     ^
horses.cpp: In function 'll getans()':
horses.cpp:142:72: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  142 |  for (auto it = s.rbegin(); k <= 30 && it != s.rend(); it++, k++) v.pb(*it);
      |                                                                        ^~~
horses.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for (int i = 1; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
horses.cpp:153:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   ll bb = stmx.get(v[i], (i + 1 == v.size() ? n - 1 : v[i + 1] - 1));
      |                           ~~~~~~^~~~~~~~~~~
horses.cpp:165:18: warning: conversion from 'std::set<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  165 |  int szs = s.size();
      |            ~~~~~~^~
horses.cpp:166:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  166 |  int szv = v.size();
      |            ~~~~~~^~
horses.cpp:167:88: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |  if (szs - (szv - ind) >= 30) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
      |                                                                                ~~~~~~~~^~~~~~~~~~~
horses.cpp:175:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |  ll bb = stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1));
      |                            ~~~~~~~~^~~~~~~~~~~
horses.cpp:178:77: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |  if (f || x > ans) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
      |                                                                     ~~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:193:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  193 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:202:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  202 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:211:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  211 |  return getans();
      |         ~~~~~~^~
#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...