제출 #1018602

#제출 시각아이디문제언어결과실행 시간메모리
1018602AmirAli_H1말 (IOI15_horses)C++17
17 / 100
1545 ms524288 KiB
// In the name of Allah #include <bits/stdc++.h> #include "horses.h" using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<ld> cld; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define kill(x) cout << x << '\n', exit(0) #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct node { int mul, mx, ind; }; const int maxn = (1 << 19) + 4; const int maxlg = 20; const int mod = 1e9 + 7; int n; pll A[maxn]; node t[2 * maxn], ca; int R; ll valx; node f(node a, node b) { node res; res.mul = 1ll * a.mul * b.mul % mod; res.mx = max(a.mx, b.mx); res.ind = max(a.ind, b.ind); return res; } pii fx(pii a, pii b) { return Mp(max(a.F, b.F), max(a.S, b.S)); } void build(int v, int tl, int tr) { if (tr - tl == 1) { t[v].mul = A[tl].F; t[v].mx = A[tl].S; if (A[tl].F == 1) t[v].ind = -1; else t[v].ind = tl; return ; } int mid = (tl + tr) / 2; build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr); t[v] = f(t[2 * v + 1], t[2 * v + 2]); } void upd(int v, int tl, int tr, int i) { if (i >= tr || i < tl) return ; if (tr - tl == 1) { t[v].mul = A[tl].F; t[v].mx = A[tl].S; if (A[tl].F == 1) t[v].ind = -1; else t[v].ind = tl; return ; } int mid = (tl + tr) / 2; upd(2 * v + 1, tl, mid, i); upd(2 * v + 2, mid, tr, i); t[v] = f(t[2 * v + 1], t[2 * v + 2]); } pll get_res(int v, int tl, int tr, int l, int r) { l = max(l, tl); r = min(r, tr); if (l >= tr || r <= tl) return Mp(ca.mx, ca.ind); if (l == tl && r == tr) return Mp(t[v].mx, t[v].ind); int mid = (tl + tr) / 2; return fx(get_res(2 * v + 1, tl, mid, l, r), get_res(2 * v + 2, mid, tr, l, r)); } int get_mul(int v, int tl, int tr, int r) { r = min(r, tr); if (r <= tl) return ca.mul; if (r == tr) return t[v].mul; int mid = (tl + tr) / 2; if (r <= mid) return get_mul(2 * v + 1, tl, mid, r); else 1ll * t[2 * v + 1].mul * get_mul(2 * v + 2, mid, tr, r) % mod; } ll get_ans(int ind) { if (ind >= R) { ll mx = 1; int j = n; while (j > 0) { pll res = get_res(0, 0, n, 0, j); int k = res.S; if (k == -1) { mx = max(mx, res.F); j = 0; } else { res = get_res(0, 0, n, k, j); mx = max(mx, (ll) res.F) * A[k].F; j = k; if (mx >= mod) break; } } R = j; valx = mx % mod; } return valx * get_mul(0, 0, n, R) % mod; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i++) A[i] = Mp(X[i], Y[i]); ca.mul = 1; ca.mx = 0; ca.ind = -1; build(0, 0, n); R = -1; return get_ans(n); } int updateX(int i, int val) { A[i].F = val; upd(0, 0, n, i); return get_ans(i); } int updateY(int i, int val) { A[i].S = val; upd(0, 0, n, i); return get_ans(i); }

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

horses.cpp: In function 'node f(node, node)':
horses.cpp:40:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |  res.mul = 1ll * a.mul * b.mul % mod;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:15:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define  F      first
      |                 ^
horses.cpp:52:20: note: in expansion of macro 'F'
   52 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                    ^
horses.cpp:16:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 | #define  S      second
      |                 ^
horses.cpp:52:39: note: in expansion of macro 'S'
   52 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                                       ^
horses.cpp: In function 'void upd(int, int, int, int)':
horses.cpp:15:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define  F      first
      |                 ^
horses.cpp:65:20: note: in expansion of macro 'F'
   65 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                    ^
horses.cpp:16:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 | #define  S      second
      |                 ^
horses.cpp:65:39: note: in expansion of macro 'S'
   65 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                                       ^
horses.cpp: In function 'int get_mul(int, int, int, int)':
horses.cpp:89:63: warning: value computed is not used [-Wunused-value]
   89 |  else 1ll * t[2 * v + 1].mul * get_mul(2 * v + 2, mid, tr, r) % mod;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'll get_ans(int)':
horses.cpp:16:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 | #define  S      second
      |                 ^
horses.cpp:97:16: note: in expansion of macro 'S'
   97 |    int k = res.S;
      |                ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:117:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |  return get_ans(n);
      |         ~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |  return get_ans(i);
      |         ~~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:129:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  129 |  return get_ans(i);
      |         ~~~~~~~^~~
horses.cpp: In function 'int get_mul(int, int, int, int)':
horses.cpp:89:30: warning: control reaches end of non-void function [-Wreturn-type]
   89 |  else 1ll * t[2 * v + 1].mul * get_mul(2 * v + 2, mid, tr, r) % 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...