| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 62909 |
2018-07-30T19:02:11 Z |
updown1 |
Horses (IOI15_horses) |
C++17 |
|
933 ms |
47556 KB |
/*
segtree. Each element i stores (X[0]*X[1]*...*X[i]*Y[i])%MOD
*/
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, P)
#define ffa ffi ffj
//#define s <<" "<<
//#define c <<" : "<<
#define w cout
#define e endl
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const ll MAXN = 500000, MOD = 1000000007;
int N, N1;
ll tree[4*MAXN+1], lazy[4*MAXN+1], xx[MAXN], yy[MAXN];
ll mI(ll x, ll y) { /// call mI(x, MOD-2)
/// x^y
if (y == 0) return 1;
if (y == 1) return x;
ll p = mI(x, y/2);
p = (p*p)%MOD;
if (y%2 == 1) p = (p*x)%MOD;
return p;
}
void push(int x, int L, int R) {
tree[x] *= lazy[x];
tree[x] %= MOD;
if (L != R) {
lazy[x*2] *= lazy[x];
lazy[x*2] %= MOD;
lazy[x*2+1] *= lazy[x];
lazy[x*2+1] %= MOD;
}
lazy[x] = 1;
}
void update(int x, int L, int R, int oL, int oR, ll v) {
push(x, L, R);
if (R < oL || oR < L) return;
if (oL <= L && R <= oR) {
lazy[x] *= v;
lazy[x] %= MOD;
push(x, L, R);
return;
}
update(x*2, L, (L+R)/2, oL, oR, v);
update(x*2+1,(L+R)/2+1,R,oL, oR, v);
tree[x] = (tree[x*2], tree[x*2+1])%MOD;
}
int answer() {
push(1, 0, N-1);
return tree[1];
}
int init(int N, int X[], int Y[]) {
N1 = N;
For (i, 0, 4*MAXN+1) tree[i] = lazy[i] = 1;
ffi xx[i] = X[i], yy[i] = Y[i];
ffi update(1, 0, N-1, i, N-1, X[i]), update(1, 0, N-1, i, i, Y[i]);
return answer();
}
int updateX(int pos, int val) {
N = N1;
update(1, 0, N-1, pos, N-1, mI(xx[pos], MOD-2));
update(1, 0, N-1, pos, N-1, val);
xx[pos] = val;
return 0;
}
int updateY(int pos, int val) {
N = N1;
update(1, 0, N-1, pos, pos, mI(yy[pos], MOD-2));
update(1, 0, N-1, pos, pos, val);
yy[pos] = val;
return 0;
}
/*
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
int main() {
_inputFile = fopen("test.in", "rb");
//_outputFile = fopen("horses.out", "w");
int N; N = _readInt();
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
X[i] = _readInt();
}
for (int i = 0; i < N; i++) {
Y[i] = _readInt();
}
printf("%d\n",init(N,X,Y));
int M; M = _readInt();
for (int i = 0; i < M; i++) {
int type; type = _readInt();
int pos; pos = _readInt();
int val; val = _readInt();
if (type == 1) {
printf("%d\n",updateX(pos,val));
} else if (type == 2) {
printf("%d\n",updateY(pos,val));
}
}
}
*/
Compilation message
horses.cpp: In function 'void update(int, int, int, int, int, ll)':
horses.cpp:57:24: warning: left operand of comma operator has no effect [-Wunused-value]
tree[x] = (tree[x*2], tree[x*2+1])%MOD;
~~~~~~~~^
horses.cpp: In function 'int answer()':
horses.cpp:61:18: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
return tree[1];
~~~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:64:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
int init(int N, int X[], int Y[]) {
^
horses.cpp:22:5: note: shadowed declaration is here
int N, N1;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
31608 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
31652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
31788 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
31788 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
933 ms |
47556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
47556 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
47556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
47556 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
47556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
