oj.uz

Submission #795430

# Submission time Handle Problem Language Result Execution time Memory
795430 2023-07-27T09:32:36 Z Cauchico Horses (IOI15_horses) C++14
37 / 100
 954 ms 68968 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
set<pair<int,int>> s;
vector<ll> x,y,tx,ty;
ll MOD = 1e9 + 7;

void Xupdate(int v, int tl, int tr, ll pos, ll val) {
	if (tl > pos or tr < pos) return;
	if (tl == tr) tx[v] = val;
	else {
		int tm = (tr+tl)/2;
		Xupdate(2*v,tl,tm,pos,val);
		Xupdate(2*v+1,tm+1,tr,pos,val);
		tx[v] = (tx[2*v]*tx[2*v+1])%MOD;
	}
}
void Yupdate(int v, int tl, int tr, ll pos, ll val) {
	if (tl > pos or tr < pos) return;
	if (tl == tr) ty[v] = val;
	else {
		int tm = (tr+tl)/2;
		Yupdate(2*v,tl,tm,pos,val);
		Yupdate(2*v+1,tm+1,tr,pos,val);
		ty[v] = max(ty[2*v],ty[2*v+1]);
	}
}
ll Xquery(int v, int tl, int tr, ll l, ll r) {
	if (tl > r or tr < l) return 1LL;
	else if (tl >= l and tr <= r) return tx[v];
	else {
		int tm = (tr+tl)/2;
		return (Xquery(2*v,tl,tm,l,r)*Xquery(2*v+1,tm+1,tr,l,r))%MOD;
	}
}
ll Yquery(int v, int tl, int tr, ll l, ll r) {
	if (tl > r or tr < l) return 0LL;
	else if (tl >= l and tr <= r) return ty[v];
	else {
		int tm = (tr+tl)/2;
		return max(Yquery(2*v,tl,tm,l,r), Yquery(2*v+1,tm+1,tr,l,r));
	}
}

int update() {
	auto can = s.end();
	for (int i=0;i<=32 and can != s.begin();i++) can--;
	while (can != s.end() and !can->first) can++;
	if (can == s.end()) return Yquery(1,0,n-1,0,n-1);
	ll ans = can->second, mxy=y[ans];
	ll px = 1;
	//cout << Yquery(1,0,n-1,0,2) << " hmm \n";
	while (can != s.end()) {
		int i = can->second;
		//cout << i << " " << px << " " << Yquery(1,0,n-1,3,3) << "\n";
		auto nxt = can; nxt++;
		int nx;
		if (nxt == s.end()) {
			nx = n-1;
		} else {
			nx = nxt->second-1;
		}
		ll xi = x[i], yi = Yquery(1,0,n-1,i,nx); 
		//cout << "i, nx, mxy " << i << " " << nx << " " << yi << "\n";
		if (px*xi > MOD or mxy < px*xi*yi) {
			ans = i; px = 1; mxy = yi;
		} else {
			px *= xi;
		}
		can++;
	}
	//cout << mxy << " " << Xquery(1,0,n-1,0,ans) << "\n";
	return (int) ((1LL*mxy*Xquery(1,0,n-1,0,ans))%MOD);
}



int init(int N, int X[], int Y[]) {
	//return 42; 
	n = N; x.resize(n); y.resize(n);
	tx.resize(4*n,1); ty.resize(4*n,0);
	for (int i=0;i<n;i++) {
		x[i] = X[i]; y[i] = Y[i];
		s.insert({x[i]>1,i});
		Xupdate(1,0,n-1,i,x[i]);
		Yupdate(1,0,n-1,i,y[i]);
	}
	//cout << Xquery(1,0,n-1,0,1) <<" ";
	return update();
}

int updateX(int pos, int val) {	
	//return 43;
	s.erase({x[pos]>1,pos});
	s.insert({val>1,pos});
	x[pos] = val;
	Xupdate(1,0,n-1,pos,val);
	return update();
	
}

int updateY(int pos, int val) {
	//return 44;
	y[pos] = val;
	Yupdate(1,0,n-1,pos,val);
	return update();
}

/*
int main() {
	freopen("horses.in", "r+",stdin);
	freopen("horses.out", "w+",stdout);
	int n_; cin >> n_;
	int X[n_], Y[n_];
	for (int i=0;i<n_;i++) {
		cin >> X[i];
	}
	for (int i=0;i<n_;i++) {
		cin >> Y[i];
	}
	cout << init(n_,X,Y) << "\n";
	int m; cin >> m;
	while (m--) {
		int a,b,c; cin >> a >> b >> c;
		if (a==1) {
			cout << updateX(b,c) << "\n";
		} else {
			cout << updateY(b,c) << "\n"; 
		}
	}
}*/

Compilation message

horses.cpp: In function 'int update()':
horses.cpp:52:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |  if (can == s.end()) return Yquery(1,0,n-1,0,n-1);
      |                             ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 296 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 4 ms 460 KB Output is correct
24 Correct 4 ms 440 KB Output is correct
25 Correct 5 ms 468 KB Output is correct
26 Correct 5 ms 464 KB Output is correct
27 Incorrect 4 ms 436 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 68968 KB Output is correct
2 Correct 954 ms 68524 KB Output is correct
3 Correct 954 ms 68604 KB Output is correct
4 Correct 907 ms 68720 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 224 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 4 ms 440 KB Output is correct
24 Correct 4 ms 452 KB Output is correct
25 Correct 3 ms 468 KB Output is correct
26 Correct 5 ms 468 KB Output is correct
27 Incorrect 4 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 300 KB Output is correct
23 Correct 4 ms 436 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 3 ms 468 KB Output is correct
26 Correct 3 ms 440 KB Output is correct
27 Incorrect 4 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -