제출 #288279

#제출 시각아이디문제언어결과실행 시간메모리
288279DystoriaX말 (IOI15_horses)C++14
0 / 100
1584 ms51656 KiB
#include "horses.h" #include <algorithm> #include <vector> #include <iostream> #include <assert.h> #include <set> #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; Node(){ val = mx = 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 = 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].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 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)); } set<int> s; int GetValue(){ int idx = 0; long long pr = 1; vector<int> path; path.emplace_back(n); auto it = s.end(); do { it = prev(it); path.emplace_back(*it); } while (it != s.begin() || path.size() < 33); for(int i = 1; i < (int) path.size(); i++){ pr *= x[path[i]]; idx = i; if(pr > MAX) break; } pr = 1; int optVal = 0, opt = 0; // int counter = 0; for(int i = idx; i; i--){ int nxt = path[i - 1] - 1; int cur_idx = max(0, path[i]); pr *= x[cur_idx]; int yval = queryMax(0, n - 1, cur_idx, nxt, 1); if(optVal < pr * yval){ opt = idx; optVal = yval; pr = 1; } } 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); if(x[i] > 1) s.insert(i); } s.insert(-1); for(int i = 0; i < n; i++) update(0, n - 1, i, y[i], 1, 1); // for(int i = 0; i < n; i++){ // cerr << i << " with previous: " << GetPrev(i) << "\n"; // } return GetValue(); } int updateX(int pos, int val) { if(x[pos] > 1) s.erase(pos); x[pos] = val; if(val > 1) s.insert(pos); 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:16:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  return (a + b) % MOD;
      |         ~~~~~~~~^~~~~
horses.cpp: In function 'int mul(long long int, long long int)':
horses.cpp:20:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |  return (a * b) % MOD;
      |         ~~~~~~~~^~~~~
horses.cpp: In function 'int GetValue()':
horses.cpp:112:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |   int yval = queryMax(0, n - 1, cur_idx, nxt, 1);
      |              ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...