제출 #513848

#제출 시각아이디문제언어결과실행 시간메모리
513848sliviu말 (IOI15_horses)C++14
100 / 100
320 ms70084 KiB
#include <bits/stdc++.h> #include "horses.h" using namespace std; const int mod = 1e9 + 7; int n, curx = 1, x[1 << 19], y[1 << 19], curinv; long double rcurx = 0, rcurinv; struct node { int val = 1, lazy = 1; long double rval, rlazy; } st[1 << 20]; void Build(int node = 1, int left = 1, int right = n) { if (left == right) { st[node].val = 1LL * (curx = (1LL * curx * x[left - 1] % mod)) * y[left - 1] % mod; st[node].rval = (rcurx += log(x[left - 1])) + log(y[left - 1]); return; } int m = (left + right) / 2; Build(2 * node, left, m), Build(2 * node + 1, m + 1, right); if (st[2 * node].rval > st[2 * node + 1].rval) st[node].rval = st[2 * node].rval, st[node].val = st[2 * node].val; else st[node].rval = st[2 * node + 1].rval, st[node].val = st[2 * node + 1].val; } void Propagate(int node, int left, int right) { if (st[node].lazy == 1) return; st[node].val = 1LL * st[node].val * st[node].lazy % mod; st[node].rval += st[node].rlazy; if (left != right) { st[2 * node].lazy = 1LL * st[2 * node].lazy * st[node].lazy % mod, st[2 * node].rlazy += st[node].rlazy; st[2 * node + 1].lazy = 1LL * st[2 * node + 1].lazy * st[node].lazy % mod, st[2 * node + 1].rlazy += st[node].rlazy; } st[node].lazy = 1, st[node].rlazy = 0; } void Update(int val, long double rval, int posleft, int posright = n, int node = 1, int left = 1, int right = n) { if (posleft <= left && right <= posright) { st[node].lazy = 1LL * st[node].lazy * val % mod; st[node].rlazy += rval; Propagate(node, left, right); return; } Propagate(node, left, right); int m = (left + right) / 2; if (posleft <= m) Update(val, rval, posleft, posright, 2 * node, left, m), Propagate(2 * node + 1, m + 1, right); if (posright > m) Update(val, rval, posleft, posright, 2 * node + 1, m + 1, right), Propagate(2 * node, left, m); if (st[2 * node].rval > st[2 * node + 1].rval) st[node].rval = st[2 * node].rval, st[node].val = st[2 * node].val; else st[node].rval = st[2 * node + 1].rval, st[node].val = st[2 * node + 1].val; } int pow(int b, int e) { int ans = 1; while (e) { if (e & 1) ans = 1LL * ans * b % mod; b = 1LL * b * b % mod, e >>= 1; } return ans; } 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]; Build(); return st[1].val; } int updateX(int pos, int val) { Update(1LL * val * pow(x[pos], mod - 2) % mod, log(val) - log(x[pos]), pos + 1); x[pos] = val; return st[1].val; } int updateY(int pos, int val) { Update(1LL * val * pow(y[pos], mod - 2) % mod, log(val) - log(y[pos]), pos + 1, pos + 1); y[pos] = val; return st[1].val; }

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

horses.cpp: In function 'void Build(int, int, int)':
horses.cpp:17:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 |   st[node].val = 1LL * (curx = (1LL * curx * x[left - 1] % mod)) * y[left - 1] % mod;
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp:17:80: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 |   st[node].val = 1LL * (curx = (1LL * curx * x[left - 1] % mod)) * y[left - 1] % mod;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Propagate(int, int, int)':
horses.cpp:32:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   32 |  st[node].val = 1LL * st[node].val * st[node].lazy % mod;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:35:63: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   35 |   st[2 * node].lazy = 1LL * st[2 * node].lazy * st[node].lazy % mod, st[2 * node].rlazy += st[node].rlazy;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:36:71: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   36 |   st[2 * node + 1].lazy = 1LL * st[2 * node + 1].lazy * st[node].lazy % mod, st[2 * node + 1].rlazy += st[node].rlazy;
      |                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Update(int, long double, int, int, int, int, int)':
horses.cpp:43:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   43 |   st[node].lazy = 1LL * st[node].lazy * val % mod;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int pow(int, int)':
horses.cpp:64:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   64 |    ans = 1LL * ans * b % mod;
      |          ~~~~~~~~~~~~~~^~~~~
horses.cpp:65:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   65 |   b = 1LL * b * b % mod, e >>= 1;
      |       ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:79:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  Update(1LL * val * pow(x[pos], mod - 2) % mod, log(val) - log(x[pos]), pos + 1);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:85:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |  Update(1LL * val * pow(y[pos], mod - 2) % mod, log(val) - log(y[pos]), pos + 1, pos + 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...