제출 #819913

#제출 시각아이디문제언어결과실행 시간메모리
819913Kerim말 (IOI15_horses)C++17
34 / 100
1583 ms28468 KiB
#include "horses.h" #include "bits/stdc++.h" using namespace std; const int MAXN = 5e5+5; const int INF = 1e9+7; int a[MAXN], b[MAXN], n; struct node{ int mul, mod; node(){ mul = mod = 0; } node(int _mul, int _mod){ mul = _mul; mod = _mod; } }s[MAXN<<2]; int ans[MAXN<<2]; node merge(node x, node y){ node z = node(0, 0); z.mul = min(x.mul * 1LL * y.mul, INF * 1LL); z.mod = (x.mod * 1LL * y.mod) % INF; return z; } void upd(int p, int nd, int x, int y){ if (x == y){ s[nd].mul = s[nd].mod = a[p]; return; } int mid = (x+y) >> 1; if (p <= mid) upd(p, nd<<1, x, mid); else upd(p, nd<<1|1, mid+1, y); s[nd] = merge(s[nd<<1], s[nd<<1|1]); } node get(int l, int r, int nd, int x, int y){ if (l > y or x > r) return node(1, 1); if (l <= x and y <= r) return s[nd]; int mid = (x+y) >> 1; return merge(get(l, r, nd<<1, x, mid), get(l, r, nd<<1|1, mid+1, y)); } int cmp(int x, int y){ if (x == y) return 0; if (x > y) swap(x, y); return b[x] < b[y] * 1LL * get(x+1, y, 1, 0, n-1).mul; } void upd1(int p, int nd, int x, int y){ if (x == y){ ans[nd] = x; return; } int mid = (x+y) >> 1; if (p <= mid) upd1(p, nd<<1, x, mid); else upd1(p, nd<<1|1, mid+1, y); if (cmp(ans[nd<<1], ans[nd<<1|1])) ans[nd] = ans[nd<<1|1]; else ans[nd] = ans[nd<<1]; } int ask(int pos){ return (get(0, pos, 1, 0, n-1).mod *1LL* b[pos]) % INF; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i++){ a[i] = X[i], b[i] = Y[i]; upd(i, 1, 0, n-1); upd1(i, 1, 0, n-1); } return ask(ans[1]); } int updateX(int pos, int val) { a[pos] = val; upd(pos, 1, 0, n-1); upd1(pos, 1, 0, n-1); return ask(ans[1]); } int updateY(int pos, int val) { b[pos] = val; upd1(pos, 1, 0, n-1); return ask(ans[1]); }

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

horses.cpp: In function 'node merge(node, node)':
horses.cpp:22:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |  z.mul = min(x.mul * 1LL * y.mul, INF * 1LL);
      |          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:23:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   23 |  z.mod = (x.mod * 1LL * y.mod) % INF;
      |          ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int ask(int)':
horses.cpp:74:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |  return (get(0, pos, 1, 0, n-1).mod *1LL* b[pos]) % INF;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
#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...