제출 #332319

#제출 시각아이디문제언어결과실행 시간메모리
332319Azert말 (IOI15_horses)C++14
17 / 100
608 ms21712 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1e9 + 4; const int MAX = 5e5 + 5; const int MOD = 1e9 + 7; int n; int x[MAX], y[MAX]; int m[MAX * 4], mm[MAX * 4], st[MAX * 4]; void initMul(int idx, int l, int r) { if (l == r) { m[idx] = mm[idx] = x[l]; return; } int mid = (l + r) / 2; initMul(idx * 2, l, mid); initMul(idx * 2 + 1, mid + 1, r); m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD; mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]); } int get(int idx, int l, int r, int posL, int posR, int type) { if (posR < l || posL > r) return 1; if (posL <= l && r <= posR) return type? m[idx] : mm[idx]; int mid = (l + r) / 2; if (type) { return (1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type)) % MOD; } return min(INF, 1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type)); } void initSt(int idx, int l, int r) { if (l == r) { st[idx] = l; return; } int mid = (l + r) / 2; initSt(idx * 2, l, mid); initSt(idx * 2 + 1, mid + 1, r); int ll = st[idx * 2]; int rr = st[idx * 2 + 1]; if (1LL * y[rr] * get(1, 0, n - 1, ll + 1, rr, 0) >= y[ll]) st[idx] = rr; else st[idx] = ll; } int get() { int pos = st[1]; return (1LL * get(1, 0, n - 1, 0, pos, 1) * y[pos]) % MOD; } void updateM(int idx, int l, int r, int pos) { if (pos < l || pos > r) return; if (l == r) { m[idx] = mm[idx] = x[pos]; return; } int mid = (l + r) / 2; updateM(idx * 2, l, mid, pos); updateM(idx * 2 + 1, mid + 1, r, pos); m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD; mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]); } void update(int idx, int l, int r, int pos) { if (pos > r || pos < l) return; if (l == r) return; int mid = (l + r) / 2; update(idx * 2, l, mid, pos); update(idx * 2 + 1, mid + 1, r, pos); int ll = st[idx * 2]; int rr = st[idx * 2 + 1]; if (1LL * y[rr] * get(1, 0, n - 1, ll + 1, rr, 0) >= y[ll]) st[idx] = rr; else st[idx] = ll; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i]; initMul(1, 0, n - 1); // exit(0); initSt(1, 0, n - 1); return get(); } int updateX(int pos, int val) { x[pos] = val; update(1, 0, n - 1, pos); return get(); } int updateY(int pos, int val) { y[pos] = val; update(1, 0, n - 1, pos); return get(); } // // #ifdef ONLINE_JUDGE // int main() { // int xx[2] = {1000000000, 1000000000}; // int yy[3] = {1000000000, 1000000000}; // cout << init(2, xx, yy) << "\n"; // // cout << updateY(1, 2) << "\n"; // } // #endif

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

horses.cpp: In function 'void initMul(int, int, int)':
horses.cpp:21:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |     m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:22:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |     mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get(int, int, int, int, int, int)':
horses.cpp:32:112: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   32 |         return (1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type)) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:34:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   34 |     return min(INF, 1LL * get(idx * 2, l, mid, posL, posR, type) * get(idx * 2 + 1, mid + 1, r, posL, posR, type));
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int get()':
horses.cpp:55:57: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   55 |     return (1LL * get(1, 0, n - 1, 0, pos, 1) * y[pos]) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void updateM(int, int, int, int)':
horses.cpp:70:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |     m[idx] = (1LL * m[idx * 2] * m[idx * 2 + 1]) % MOD;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:71:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |     mm[idx] = min(INF, 1LL * mm[idx * 2 + 1] * mm[idx * 2]);
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...