제출 #309521

#제출 시각아이디문제언어결과실행 시간메모리
309521mihai145말 (IOI15_horses)C++14
17 / 100
607 ms53068 KiB
#include "horses.h" #include <set> #include <vector> #include <algorithm> const int YMAX = 1e9; const int MOD = 1e9 + 7; const int NMAX = 5e5; int n; long long x[NMAX + 2], y[NMAX + 2]; struct Aintx { long long v[4 * NMAX]; void Build(int node, int st, int dr) { if(st == dr) { v[node] = x[st]; return ; } int mid = (st + dr) >> 1; Build(2 * node, st, mid); Build(2 * node + 1, mid + 1, dr); v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD; } void setx(int node, int st, int dr, int pos, long long val) { if(st == dr) { v[node] = val; return; } int mid = (st + dr) >> 1; if(pos <= mid) setx(2 * node, st, mid, pos, val); else setx(2 * node + 1, mid + 1, dr, pos, val); v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD; } long long queryx(int node, int st, int dr, int l, int r) { if(st > dr) return 0; if(l <= st && dr <= r) return v[node]; if(dr < l || st > r) return 1; int mid = (st + dr) >> 1; long long ans1 = queryx(2 * node, st, mid, l, r); long long ans2 = queryx(2 * node + 1, mid + 1, dr, l, r); return (1LL * ans1 * ans2) % MOD; } }; Aintx aintx; struct Ainty { long long v[4 * NMAX]; void Build(int node, int st, int dr) { if(st == dr) { v[node] = y[st]; return ; } int mid = (st + dr) >> 1; Build(2 * node, st, mid); Build(2 * node + 1, mid + 1, dr); v[node] = std::max(v[2 * node], v[2 * node + 1]); } void sety(int node, int st, int dr, int pos, long long val) { if(st == dr) { v[node] = val; return; } int mid = (st + dr) >> 1; if(pos <= mid) sety(2 * node, st, mid, pos, val); else sety(2 * node + 1, mid + 1, dr, pos, val); v[node] = std::max(v[2 * node], v[2 * node + 1]); } long long queryy(int node, int st, int dr, int l, int r) { if(st > dr) return 0; if(l <= st && dr <= r) return v[node]; if(dr < l || st > r) return 0; int mid = (st + dr) >> 1; int ans1 = queryy(2 * node, st, mid, l, r); int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r); return std::max(ans1, ans2); } }; Ainty ainty; std::set <int> s; int Query() { long long prod = 1LL; std::vector <int> pos; for(auto it : s) { pos.push_back(-it); prod *= x[-it]; if(prod >= YMAX) break; } int sz = (int)pos.size(); long long px = 1LL, mx = 0LL, py; for(int i = sz - 2; i >= 0; i--) { px *= x[pos[i]]; if(i) py = ainty.queryy(1, 1, n, pos[i], pos[i - 1] - 1); else py = ainty.queryy(1, 1, n, pos[i], n); mx = std::max(mx, px * py); } if(pos.back() == -1) { py = ainty.queryy(1, 1, n, 1, n); return std::max(mx, py); } if(sz > 1) py = ainty.queryy(1, 1, n, pos[sz - 1], pos[sz - 2] - 1); else py = ainty.queryy(1, 1, n, pos[sz - 1], n); return (1LL * std::max(mx, py) * aintx.queryx(1, 1, n, 1, pos[sz - 1])) % MOD; } int init(int N, int X[], int Y[]) { n = N; x[0] = 1LL; y[0] = 1LL; for(int i = 0; i < n; i++) x[i + 1] = X[i], y[i + 1] = Y[i]; aintx.Build(1, 1, n); ainty.Build(1, 1, n); s.insert(0); for(int i = 1; i <= n; i++) { if(x[i] > 1) { s.insert(-i); } } return Query(); } int updateX(int pos, int val) { pos++; if(x[pos] == val) return Query(); aintx.setx(1, 1, n, pos, val); if(x[pos] > 1 && val == 1) s.erase(-pos); else if(x[pos] == 1 && val > 1) s.insert(-pos); x[pos] = val; return Query(); } int updateY(int pos, int val) { pos++; if(y[pos] == val) return Query(); ainty.sety(1, 1, n, pos, val); y[pos] = val; return Query(); }

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

horses.cpp: In member function 'long long int Ainty::queryy(int, int, int, int, int)':
horses.cpp:117:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  117 |             int ans1 = queryy(2 * node, st, mid, l, r);
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:118:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  118 |             int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r);
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int Query()':
horses.cpp:158:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 |             return std::max(mx, py);
      |                    ~~~~~~~~^~~~~~~~
horses.cpp:166:77: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  166 |     return (1LL * std::max(mx, py) * aintx.queryx(1, 1, n, 1, pos[sz - 1])) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
#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...