제출 #288173

#제출 시각아이디문제언어결과실행 시간메모리
288173DystoriaX말 (IOI15_horses)C++14
34 / 100
1592 ms40056 KiB
#include "horses.h" #include <algorithm> #include <vector> #include <iostream> #define lc (i << 1) #define rc (1 | (i << 1)) using namespace std; const int MOD = 1e9 + 7; int add(long long a, long long b){ return (a + b) % MOD; } int mul(long long a, long long b){ return (a * b) % MOD; } struct Node{ int val, mx; long long prod; Node(){ val = mx = prod = 0; } }; Node st[4 * 500010]; int n; vector<int> x, y; const int MAX = 1e9; void update(int l, int r, int pt, int val, int type, int i){ if(r < pt || pt < l) return; if(l == r && l == pt){ if(type == 0) st[i].val = st[i].prod = val; else st[i].mx = val; return; } int m = (l + r) >> 1; update(l, m, pt, val, type, lc); update(m + 1, r, pt, val, type, rc); st[i].val = mul(st[lc].val, st[rc].val); st[i].prod = min(st[lc].prod * st[rc].prod, MAX + 1LL); st[i].mx = max(st[lc].mx, st[rc].mx); } int query(int l, int r, int ls, int rs, int i){ if(r < ls || rs < l) return 1; if(ls <= l && r <= rs) return st[i].val; int m = (l + r) >> 1; return mul(query(l, m, ls, rs, lc), query(m + 1, r, ls, rs, rc)); } long long queryProd(int l, int r, int ls, int rs, int i){ if(r < ls || rs < l) return 1; if(ls <= l && r <= rs) return st[i].prod; int m = (l + r) >> 1; return min(queryProd(l, m, ls, rs, lc) * queryProd(m + 1, r, ls, rs, rc), MAX + 1LL); } long long queryMax(int l, int r, int ls, int rs, int i){ if(r < ls || rs < l) return 0; if(ls <= l && r <= rs) return st[i].mx; int m = (l + r) >> 1; return max(queryMax(l, m, ls, rs, lc), queryMax(m + 1, r, ls, rs, rc)); } int GetNext(int idx){ int l = idx, r = n - 1; while(l <= r){ int m = (l + r) >> 1; if(queryProd(0, n - 1, idx, m, 1) == x[idx]) l = m + 1; else r = m - 1; } return r; } int GetValue(){ int idx = 0; int l = 0, r = n - 1; while(l <= r){ int m = (l + r) >> 1; if(queryProd(0, n - 1, m, n - 1, 1) == MAX + 1) l = m + 1; else r = m - 1; } idx = max(0, r); long long pr = 1; int optVal = 0, opt; while(true){ int nxt = GetNext(idx); pr *= x[idx]; int yval = queryMax(0, n - 1, idx, nxt, 1); if(optVal < pr * yval){ opt = idx; optVal = yval; pr = 1; } idx = nxt + 1; if(idx == n) break; } return mul(query(0, n - 1, 0, opt, 1), optVal); } int init(int N, int X[], int Y[]) { n = N; x.insert(x.begin(), X, X + N); y.insert(y.begin(), Y, Y + N); for(int i = 0; i < n; i++) update(0, n - 1, i, x[i], 0, 1); for(int i = 0; i < n; i++) update(0, n - 1, i, y[i], 1, 1); // cerr << GetNext(0) << "\n"; return GetValue(); } int updateX(int pos, int val) { x[pos] = val; update(0, n - 1, pos, val, 0, 1); return GetValue(); } int updateY(int pos, int val) { y[pos] = val; update(0, n - 1, pos, val, 1, 1); return GetValue(); }

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

horses.cpp: In function 'int add(long long int, long long int)':
horses.cpp:14:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   14 |  return (a + b) % MOD;
      |         ~~~~~~~~^~~~~
horses.cpp: In function 'int mul(long long int, long long int)':
horses.cpp:18:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 |  return (a * b) % MOD;
      |         ~~~~~~~~^~~~~
horses.cpp: In constructor 'Node::Node()':
horses.cpp:26:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   26 |   val = mx = prod = 0;
      |              ~~~~~^~~
horses.cpp: In function 'void update(int, int, int, int, int, int)':
horses.cpp:40:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |   if(type == 0) st[i].val = st[i].prod = val;
      |                             ~~~~~~~~~~~^~~~~
horses.cpp: In function 'int GetValue()':
horses.cpp:119:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |   int yval = queryMax(0, n - 1, idx, nxt, 1);
      |              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:132:18: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |  return mul(query(0, n - 1, 0, opt, 1), optVal);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...