제출 #795427

#제출 시각아이디문제언어결과실행 시간메모리
795427JosiaHorses (IOI15_horses)C++17
0 / 100
686 ms73064 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define int long long constexpr ll mod = 1e9+7; struct seg { // vector<int> tree; array<signed, 2000000> tree; void init(int n) { // tree.assign(n*4, 0); } void update(int v, int rl, int rr, int pos, int x) { if (rl == rr) { tree[v] = x; return; } int rm = (rl + rr)/2; if (pos <= rm) update(v*2, rl, rm, pos, x); else update(v*2+1, rm+1, rr, pos, x); tree[v] = max(tree[v*2], tree[v*2+1]); } int query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return 0; if (rl == ql && rr == qr) return tree[v]; int rm = (rl + rr)/2; return max(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr)); } }; struct segY { vector<pair<int, int>> tree; void init(int n) { tree.assign(n*4, {0, 0}); } void update(int v, int rl, int rr, int pos, int x) { if (rl == rr) { tree[v] = {x, pos}; return; } int rm = (rl + rr)/2; if (pos <= rm) update(v*2, rl, rm, pos, x); else update(v*2+1, rm+1, rr, pos, x); tree[v] = max(tree[v*2], tree[v*2+1]); } pair<int, int> query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return {0, -1}; if (rl == ql && rr == qr) return tree[v]; int rm = (rl + rr)/2; return max(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr)); } }; ll mult(ll a, ll b) { int res = a*b; if (res >= mod) res%=mod; return res; } struct seg2 { vector<ll> tree; void init(int n) { tree.assign(n*4, 0); } void update(int v, int rl, int rr, int pos, int x) { if (rl == rr) { tree[v] = x; return; } int rm = (rl + rr)/2; if (pos <= rm) update(v*2, rl, rm, pos, x); else update(v*2+1, rm+1, rr, pos, x); tree[v] = mult(tree[v*2], tree[v*2+1]); } ll query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return 1; if (rl == ql && rr == qr) return tree[v]; int rm = (rl + rr)/2; return mult(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr)); } }; struct rightestNonZero { // vector<int> tree; array<signed, 2000000> tree; void init(int n) { // tree.assign(n*4, 0); } void update(int v, int rl, int rr, int pos, int x) { if (rl == rr) { tree[v] = x?pos:-1; return; } int rm = (rl + rr)/2; if (pos <= rm) update(v*2, rl, rm, pos, x); else update(v*2+1, rm+1, rr, pos, x); tree[v] = max(tree[v*2], tree[v*2+1]); } int query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return 0; if (rl == ql && rr == qr) return tree[v]; int rm = (rl + rr)/2; return max(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr)); } }; struct leftestNonZero { // vector<int> tree; array<signed, 2000000> tree; void init(int n) { // tree.assign(n*4, 0); } void update(int v, int rl, int rr, int pos, int x) { if (rl == rr) { tree[v] = x?pos:1e9; return; } int rm = (rl + rr)/2; if (pos <= rm) update(v*2, rl, rm, pos, x); else update(v*2+1, rm+1, rr, pos, x); tree[v] = min(tree[v*2], tree[v*2+1]); } int query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return 0; if (rl == ql && rr == qr) return tree[v]; int rm = (rl + rr)/2; return min(query(v*2, rl, rm, ql, min(qr, rm)), query(v*2+1, rm+1, rr, max(ql, rm+1), qr)); } }; seg tree; segY treeY; seg2 tree2; leftestNonZero lnz; rightestNonZero rnz; int N; vector<ll> X, Y; struct getSol { int sol = 0; int BS(int pos) { if (pos == 0) return -1; int res = rnz.query(1, 0, N-1, 0, pos-1); if (res==-1) return 0; return res; int l = 0, r = pos-1; while (l<r) { int m = (l+r+1)/2; if (tree.query(1, 0, N-1, m, pos-1) > 1) { l = m; } else { r = m-1; } } return l; } int BSinv(int pos) { if (pos == N-1) return N-1; int res = lnz.query(1, 0, N-1, pos+1, N-1); return res; int l = pos+1, r = N-1; while (l<r) { int m = (l+r+1)/2; if (tree.query(1, 0, N-1, pos+1, m) > 1) { r = m-1; } else { l = m; } } return l; } int findInd() { int currInd = N-1; ll currProd = 1; for (int i = N-1; i>=0; i = BS(i)) { auto bestSell = treeY.query(1, 0, N-1, i, BSinv(i)); if (currProd*Y[currInd] <= bestSell.first) {currInd = bestSell.second; currProd=1;} currProd *= X[i]; if (currProd*Y[currInd] > 1e9) break; } return currInd; } getSol() { int ind = findInd(); sol = (tree2.query(1, 0, N-1, 0, ind) * Y[ind])%mod; } }; signed init(signed _N, signed _X[], signed _Y[]) { N = _N; X.resize(N); Y.resize(N); for (int i = 0; i<N; i++) X[i] = _X[i]; for (int i = 0; i<N; i++) Y[i] = _Y[i]; tree.init(N); treeY.init(N); tree2.init(N); for (int i = 0; i<N; i++) { lnz.update(1, 0, N-1, i, X[i]>1); rnz.update(1, 0, N-1, i, X[i]>1); tree.update(1, 0, N-1, i, X[i]); treeY.update(1, 0, N-1, i, Y[i]); tree2.update(1, 0, N-1, i, X[i]); } return getSol().sol; } signed updateX(signed pos, signed val) { tree.update(1, 0, N-1, pos, val); tree2.update(1, 0, N-1, pos, val); lnz.update(1, 0, N-1, pos, val>1); rnz.update(1, 0, N-1, pos, val>1); X[pos] = val; return getSol().sol; } signed updateY(signed pos, signed val) { treeY.update(1, 0, N-1, pos, val); Y[pos] = val; return getSol().sol; }

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

horses.cpp: In member function 'void seg::init(long long int)':
horses.cpp:15:16: warning: unused parameter 'n' [-Wunused-parameter]
   15 |  void init(int n) {
      |                ^
horses.cpp: In member function 'void seg::update(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:21:14: warning: conversion from 'long long int' to 'std::array<int, 2000000>::value_type' {aka 'int'} may change value [-Wconversion]
   21 |    tree[v] = x;
      |              ^
horses.cpp: In member function 'void rightestNonZero::init(long long int)':
horses.cpp:120:16: warning: unused parameter 'n' [-Wunused-parameter]
  120 |  void init(int n) {
      |                ^
horses.cpp: In member function 'void rightestNonZero::update(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:126:15: warning: conversion from 'long long int' to 'std::array<int, 2000000>::value_type' {aka 'int'} may change value [-Wconversion]
  126 |    tree[v] = x?pos:-1;
      |              ~^~~~~~~
horses.cpp: In member function 'void leftestNonZero::init(long long int)':
horses.cpp:153:16: warning: unused parameter 'n' [-Wunused-parameter]
  153 |  void init(int n) {
      |                ^
horses.cpp: In member function 'void leftestNonZero::update(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:159:16: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  159 |    tree[v] = x?pos:1e9;
      |                ^~~
horses.cpp:159:15: warning: conversion from 'double' to 'std::array<int, 2000000>::value_type' {aka 'int'} may change value [-Wfloat-conversion]
  159 |    tree[v] = x?pos:1e9;
      |              ~^~~~~~~~
horses.cpp: In member function 'long long int getSol::findInd()':
horses.cpp:246:16: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  246 |    if (currProd*Y[currInd] > 1e9) break;
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:280:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  280 |  return getSol().sol;
      |         ~~~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:292:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  292 |  return getSol().sol;
      |         ~~~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:299:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  299 |  return getSol().sol;
      |         ~~~~~~~~~^~~
#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...