oj.uz

Submission #924836

# Submission time Handle Problem Language Result Execution time Memory
924836 2024-02-09T21:52:41 Z Macker Horses (IOI15_horses) C++17
17 / 100
 275 ms 91316 KB 
#include "horses.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
typedef long double ld;
#define fi first
#define se second

ll mod = 1e9 + 7;
vector<pair<ll, ld>> st;
vector<pair<ll, ld>> lz;
vector<ll> x;
vector<ll> y;
int n;
int len = 1;

ll pow(ll n, ll k){
	n %= mod;
	ll res = 1;
	while(k > 0){
		if(k % 2) res = res * n % mod;
		k /= 2;
		n = n * n % mod;
	}
	return res;
}

ll modInv(ll x){
	return pow(x, mod - 2);
}

void prop(int i){
	st[i * 2].fi = st[i * 2].fi * lz[i].fi % mod;
	st[i * 2].se += lz[i].se;
	lz[i * 2].fi = lz[i * 2].fi * lz[i].fi % mod;
	lz[i * 2].se += lz[i].se;
	st[i * 2 + 1].fi = st[i * 2 + 1].fi * lz[i].fi % mod;
	st[i * 2 + 1].se += lz[i].se;
	lz[i * 2 + 1].fi = lz[i * 2 + 1].fi * lz[i].fi % mod;
	lz[i * 2 + 1].se += lz[i].se;
}

void upd(int l, int r, ll mval, ld lval, int i = 1, int s = 0, int e = len){
	if(l >= e || s >= r) return;
	if(l <= s && e <= r){
		st[i].fi = st[i].fi * mval % mod;
		st[i].se += lval;
		lz[i].fi = lz[i].fi * mval % mod;
		lz[i].se += lval;
		return;
	}
	prop(i);
	upd(l, r, mval, lval, i * 2, s, (s + e) / 2);
	upd(l, r, mval, lval, i * 2 + 1, (s + e) / 2, e);
	if(st[i * 2].second > st[i * 2 + 1].second){
		st[i] = st[i * 2];
	}
	else st[i] = st[i * 2 + 1];
}

int init(int N, int X[], int Y[]) {
	x.assign(X, X + N);
	y.assign(Y, Y + N);
	n = N;

	while(len < N) len *= 2;
	st.resize(2 * len, {1, 0});
	lz.resize(2 * len, {1, 0});

	for (int i = 0; i < N; i++) {
		st[len + i].fi = st[len + i - 1].fi * x[i] % mod;
		st[len + i].second = st[len + i - 1].se + logl(x[i]);
	}
	for (int i = 0; i < N; i++) {
		st[len + i].fi = st[len + i].fi * y[i] % mod;
		st[len + i].se += logl(y[i]);
	}
	
	for (int i = len - 1; i > 0; i--) {
		if(st[i * 2].second > st[i * 2 + 1].second){
			st[i] = st[i * 2];
		}
		else st[i] = st[i * 2 + 1];
	}
	
	
	return st[1].first;
}

int updateX(int pos, int val) {
	upd(pos, len + 1, val * modInv(x[pos]) % mod, logl(val) - logl(x[pos]));
	x[pos] = val;

	return st[1].first;
}

int updateY(int pos, int val) {
	upd(pos, pos + 1, val * modInv(y[pos]) % mod, logl(val) - logl(y[pos]));
	y[pos] = val;

	return st[1].first;
}

Compilation message

horses.cpp: In function 'll pow(ll, ll)':
horses.cpp:19:11: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   19 | ll pow(ll n, ll k){
      |        ~~~^
horses.cpp:16:5: note: shadowed declaration is here
   16 | int n;
      |     ^
horses.cpp: In function 'll modInv(ll)':
horses.cpp:30:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   30 | ll modInv(ll x){
      |           ~~~^
horses.cpp:14:12: note: shadowed declaration is here
   14 | vector<ll> x;
      |            ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:89:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return st[1].first;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:96:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  return st[1].first;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |  return st[1].first;

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 436 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 400 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 432 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 1 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 82428 KB Output is correct
2 Incorrect 275 ms 91316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 436 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Incorrect 1 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 432 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Incorrect 1 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -