oj.uz

Submission #641868

# Submission time Handle Problem Language Result Execution time Memory
641868 2022-09-17T17:35:27 Z QwertyPi Horses (IOI15_horses) C++14
37 / 100
 718 ms 48532 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;


ll N;

namespace RMQ{
	int t[MAXN * 4] = {0};
	void upd(int pos, int val, int v = 0, int tl = 0, int tr = N - 1){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm){
			upd(pos, val, v * 2 + 1, tl, tm);
		}else{
			upd(pos, val, v * 2 + 2, tm + 1, tr);
		}
		t[v] = std::max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	int max(int l, int r, int v = 0, int tl = 0, int tr = N - 1){
		if(r < tl || tr < l) return 0;
		if(l <= tl && tr <= r) return t[v];
		int tm = (tl + tr) / 2;
		return std::max(max(l, r, v * 2 + 1, tl, tm),
				max(l, r, v * 2 + 2, tm + 1, tr));
	}
};

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) % MOD; }
ll mi(ll a) { return bp(a, MOD - 2); }

ll query() {
	ll ans = 1, rans = 1;
	ll c = 1;
	auto ptr = --n1.end();
	while(ptr != n1.begin() && c <= MOD){
		ptr--; c *= x[*ptr];
	}
	c = 1;
	for(; ptr != --n1.end(); ptr++){
		int v = RMQ::max(*ptr, *next(ptr) - 1);
		if(c * v > ans){
			ans = c * v;
			rans = bit_add.qry(*ptr) > 0 ? 0 : mul(bit_mul.qry(*ptr), v);
		}
		c *= x[*next(ptr)];
	}
	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]);
	}
	
	n1.insert(0); n1.insert(N);
	for(int i = 0; i < N; i++){
		if(x[i] != 1) n1.insert(i);
	}
	
	for(int i = 0; i < N; i++){
		RMQ::upd(i, y[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 && pos != 0) 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;
	RMQ::upd(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: At global scope:
horses.cpp:42:63: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  void upd(int pos, int val, int v = 0, int tl = 0, int tr = N - 1){
      |                                                             ~~^~~
horses.cpp:55:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   55 |  int max(int l, int r, int v = 0, int tl = 0, int tr = N - 1){
      |                                                        ~~^~~
horses.cpp: In function 'long long int add(long long int, long long int)':
horses.cpp:67:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   67 | 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:67:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   67 | 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:68:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   68 | 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:68:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   68 | 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 'long long int query()':
horses.cpp:81:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |   int v = RMQ::max(*ptr, *next(ptr) - 1);
      |                    ^~~~
horses.cpp:81:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |   int v = RMQ::max(*ptr, *next(ptr) - 1);
      |                          ~~~~~~~~~~~^~~
horses.cpp:81:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |   int v = RMQ::max(*ptr, *next(ptr) - 1);
      |                                        ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:91:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   91 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:38:4: note: shadowed declaration is here
   38 | ll N;
      |    ^
horses.cpp:110:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |   RMQ::upd(i, y[i]);
      |               ~~~^
horses.cpp:110:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |   RMQ::upd(i, y[i]);
      |                   ^
horses.cpp:112:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |  RMQ::upd(pos, val);
      |                   ^
horses.cpp:129:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  129 |  return query();
      |         ~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8056 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 4 ms 8148 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct
11 Correct 5 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 4 ms 8144 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 4 ms 8116 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 4 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 4 ms 8148 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 4 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 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 5 ms 8148 KB Output is correct
17 Correct 4 ms 8020 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 4 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 5 ms 8148 KB Output is correct
24 Correct 5 ms 8148 KB Output is correct
25 Correct 6 ms 8240 KB Output is correct
26 Correct 5 ms 8148 KB Output is correct
27 Correct 9 ms 8148 KB Output is correct
28 Correct 6 ms 8148 KB Output is correct
29 Incorrect 5 ms 8176 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 48456 KB Output is correct
2 Correct 392 ms 48412 KB Output is correct
3 Correct 412 ms 48532 KB Output is correct
4 Correct 503 ms 48420 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 4 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 4 ms 8148 KB Output is correct
7 Correct 5 ms 8164 KB Output is correct
8 Correct 4 ms 8148 KB Output is correct
9 Correct 4 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 8148 KB Output is correct
13 Correct 5 ms 8052 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 4 ms 8148 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 4 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 6 ms 8148 KB Output is correct
24 Correct 5 ms 8148 KB Output is correct
25 Correct 7 ms 8148 KB Output is correct
26 Correct 6 ms 8232 KB Output is correct
27 Correct 10 ms 8204 KB Output is correct
28 Correct 6 ms 8172 KB Output is correct
29 Incorrect 5 ms 8148 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 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 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 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 5 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 4 ms 8148 KB Output is correct
18 Correct 5 ms 8148 KB Output is correct
19 Correct 4 ms 8144 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 4 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 5 ms 8148 KB Output is correct
24 Correct 5 ms 8148 KB Output is correct
25 Correct 6 ms 8168 KB Output is correct
26 Correct 5 ms 8148 KB Output is correct
27 Correct 9 ms 8096 KB Output is correct
28 Correct 6 ms 8148 KB Output is correct
29 Incorrect 5 ms 8152 KB Output isn't correct
30 Halted 0 ms 0 KB -