oj.uz

Submission #641860

# Submission time Handle Problem Language Result Execution time Memory
641860 2022-09-17T17:13:26 Z QwertyPi Horses (IOI15_horses) C++14
17 / 100
 294 ms 57060 KB 
#include "horses.h"


#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MOD = 1e9 + 7;

const ll MAXN = 5e5 + 11;

ll x[MAXN], y[MAXN];

struct BIT{
	ll bit[MAXN] = {0}, id;
	void init(ll id, ll (*f)(ll, ll)) { 
		this->id = id; 
		fill(bit, bit + MAXN, id);
		combine = f;
	}
	void add(ll pos, ll val){
		pos++;
		for(ll i = pos; i < MAXN; i += i & -i){
			bit[i] = combine(bit[i], val);
		}
	}
	ll qry(ll pos){
		pos++; ll ret = id;
		for(ll i = pos; i; i -= i & -i){
			ret = combine(ret, bit[i]);
		}
		return ret;
	}
	ll (*combine)(ll, ll);
} bit_add, bit_mul;

struct RMQ{
	
};

ll N;
set<ll> n1;


ll add(ll x, ll y) { return x + y; }
ll mul(ll x, ll y) { return x * y % MOD; }
ll bp(ll a, ll b) { if(b == 0) return 1; return bp(a * a % MOD, b / 2) * (b % 2 ? a : 1); }
ll mi(ll a) { return bp(a, MOD - 2); }

ll query() {
	ll ans = 1, rans = 1;
	ll c = 1;
	ll i;
	for(i = N - 1; i >= 0; i--){
		if(i == -1) break;
		c *= x[i];
		if(c > MOD) break;
	}
	c = 1;
	for(; i < N; i++){
		if(c * y[i] > ans){
			ans = c * y[i];
			rans = bit_add.qry(i) > 0 ? 0 : mul(bit_mul.qry(i), y[i]);
		}
		c *= x[i + 1];
	}
	return rans;
}

int init(int N, int X[], int Y[]) {
	::N = N;
	bit_add.init(0, add);
	bit_mul.init(1, mul);
	
	for(int i = 0; i < N; i++) x[i] = X[i];
	for(int i = 0; i < N; i++) y[i] = Y[i];

	for(int i = 0; i < N; i++){
		if(x[i] == MOD) bit_add.add(i, 1);
		else bit_mul.add(i, x[i]);
	}

	for(int i = 0; i < N; i++){
		if(x[i] != 1) n1.insert(i);
	}
	return query();
}

int updateX(int pos, int val) {	
	if(x[pos] == MOD) bit_add.add(pos, -1);
	else bit_mul.add(pos, mi(x[pos]));
	if(x[pos] != 1) n1.erase(pos);
	x[pos] = val;
	if(x[pos] == MOD) bit_add.add(pos, 1);
	else bit_mul.add(pos, x[pos]);
	if(x[pos] != 1) n1.insert(pos);
	return query();
}

int updateY(int pos, int val) {
	y[pos] = val;
	return query();
}

Compilation message

horses.cpp: In member function 'void BIT::init(long long int, long long int (*)(long long int, long long int))':
horses.cpp:16:15: warning: declaration of 'id' shadows a member of 'BIT' [-Wshadow]
   16 |  void init(ll id, ll (*f)(ll, ll)) {
      |               ^
horses.cpp:15:22: note: shadowed declaration is here
   15 |  ll bit[MAXN] = {0}, id;
      |                      ^~
horses.cpp: In function 'long long int add(long long int, long long int)':
horses.cpp:45:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   45 | ll add(ll x, ll y) { return x + y; }
      |                 ^
horses.cpp:12:13: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |             ^
horses.cpp:45:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   45 | ll add(ll x, ll y) { return x + y; }
      |           ^
horses.cpp:12:4: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |    ^
horses.cpp: In function 'long long int mul(long long int, long long int)':
horses.cpp:46:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   46 | ll mul(ll x, ll y) { return x * y % MOD; }
      |                 ^
horses.cpp:12:13: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |             ^
horses.cpp:46:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   46 | ll mul(ll x, ll y) { return x * y % MOD; }
      |           ^
horses.cpp:12:4: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:70:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   70 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:41:4: note: shadowed declaration is here
   41 | ll N;
      |    ^
horses.cpp:86:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:97:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:102:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  return query();
      |         ~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 48144 KB Output is correct
2 Incorrect 294 ms 57060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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