oj.uz

Submission #590793

# Submission time Handle Problem Language Result Execution time Memory
590793 2022-07-06T11:16:33 Z FatihSolak Horses (IOI15_horses) C++17
100 / 100
 1287 ms 60804 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define N 500005
using namespace std;
const int mod = 1e9 + 7;
struct SegTree1{
	vector<int> t;
	int n;
	void init(int size){
		n = size;
		t.assign(4*n,0);
	}
	void upd(int v,int tl,int tr,int pos,int val){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm){
			upd(v*2,tl,tm,pos,val);
		}
		else upd(v*2+1,tm+1,tr,pos,val);
		t[v] = (long long)t[v*2]*t[v*2+1]%mod;
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl){
			return 1;
		}
		if(l <= tl && tr <= r){
			return t[v];
		}
		int tm = (tl + tr)/2;
		return (long long)get(v*2,tl,tm,l,r)*get(v*2+1,tm+1,tr,l,r)%mod;
	}
	void upd(int pos,int val){
		upd(1,0,n-1,pos,val);
	}
	int get(int l,int r){
		return get(1,0,n-1,l,r);
	}
}tree1;
struct SegTree2{
	vector<int> t;
	int n;
	void init(int size){
		n = size;
		t.assign(4*n,0);
	}
	void upd(int v,int tl,int tr,int pos,int val){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm){
			upd(v*2,tl,tm,pos,val);
		}
		else upd(v*2+1,tm+1,tr,pos,val);
		t[v] = max(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl){
			return 1;
		}
		if(l <= tl && tr <= r){
			return t[v];
		}
		int tm = (tl + tr)/2;
		return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int pos,int val){
		upd(1,0,n-1,pos,val);
	}
	int get(int l,int r){
		return get(1,0,n-1,l,r);
	}
}tree2;
const int BOUND = 1e9;
set<int> s;
int x[N],y[N];
int n;
int get_ans(){
	int l = 0;
	long long prod = 1;
	if(s.size()){
		auto it = prev(s.end());
		while(prod < BOUND){
			prod *= x[*it];
			if(prod >= BOUND){
				l = *it;
			}
			if(it == s.begin())break;
			it = prev(it);
		}
	}
	int tmp = l;
	int opt = l;
	long long val = 0;
	prod = 1;
	while(1){
		if(l != tmp){
			prod *= x[l];
		}
		auto foo = tree2.get(l,n-1);
		if(prod * foo > val){
			val = prod * foo;
			opt = l;
		}
		if(s.upper_bound(l) == s.end())break;
		l = *s.upper_bound(l);
	}
	return (long long)tree2.get(opt,n-1) * tree1.get(0,opt) % mod;
}
int init(int n_, int X[], int Y[]) {
	n = n_;
	tree1.init(n);
	tree2.init(n);
	for(int i = 0;i<n;i++){
		x[i] = X[i];
		y[i] = Y[i];
		tree1.upd(i,x[i]);
		tree2.upd(i,y[i]);
		if(x[i] > 1){
			s.insert(i);
		}
	}
	return get_ans();
}

int updateX(int pos, int val) {	
	if(x[pos] > 1){
		s.erase(pos);
	}
	x[pos] = val;
	tree1.upd(pos,x[pos]);
	if(x[pos] > 1){
		s.insert(pos);
	}
	return get_ans();
}

int updateY(int pos, int val) {
	y[pos] = val;
	tree2.upd(pos,y[pos]);
	return get_ans();
}

Compilation message

horses.cpp: In member function 'void SegTree1::upd(int, int, int, int, int)':
horses.cpp:23:36: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   23 |   t[v] = (long long)t[v*2]*t[v*2+1]%mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int SegTree1::get(int, int, int, int, int)':
horses.cpp:33:62: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |   return (long long)get(v*2,tl,tm,l,r)*get(v*2+1,tm+1,tr,l,r)%mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int get_ans()':
horses.cpp:112:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return (long long)tree2.get(opt,n-1) * tree1.get(0,opt) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 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 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 0 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 380 KB Output is correct
32 Correct 2 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 48348 KB Output is correct
2 Correct 402 ms 60804 KB Output is correct
3 Correct 472 ms 52028 KB Output is correct
4 Correct 541 ms 55764 KB Output is correct

Subtask #4
23.0 / 23.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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 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 0 ms 212 KB Output is correct
10 Correct 1 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 0 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 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 3 ms 340 KB Output is correct
33 Correct 156 ms 23880 KB Output is correct
34 Correct 148 ms 23940 KB Output is correct
35 Correct 293 ms 47372 KB Output is correct
36 Correct 286 ms 47276 KB Output is correct
37 Correct 169 ms 24072 KB Output is correct
38 Correct 229 ms 35856 KB Output is correct
39 Correct 168 ms 23720 KB Output is correct
40 Correct 266 ms 47272 KB Output is correct
41 Correct 154 ms 23964 KB Output is correct
42 Correct 175 ms 23820 KB Output is correct
43 Correct 262 ms 47192 KB Output is correct
44 Correct 260 ms 47312 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 296 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 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
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 1282 ms 48188 KB Output is correct
34 Correct 436 ms 60716 KB Output is correct
35 Correct 447 ms 51980 KB Output is correct
36 Correct 595 ms 55848 KB Output is correct
37 Correct 162 ms 27824 KB Output is correct
38 Correct 161 ms 27824 KB Output is correct
39 Correct 301 ms 58228 KB Output is correct
40 Correct 283 ms 58144 KB Output is correct
41 Correct 177 ms 26228 KB Output is correct
42 Correct 255 ms 38744 KB Output is correct
43 Correct 139 ms 25852 KB Output is correct
44 Correct 307 ms 53152 KB Output is correct
45 Correct 159 ms 25896 KB Output is correct
46 Correct 167 ms 25876 KB Output is correct
47 Correct 305 ms 53592 KB Output is correct
48 Correct 280 ms 53632 KB Output is correct
49 Correct 251 ms 30824 KB Output is correct
50 Correct 227 ms 30912 KB Output is correct
51 Correct 576 ms 60156 KB Output is correct
52 Correct 330 ms 59596 KB Output is correct
53 Correct 632 ms 29156 KB Output is correct
54 Correct 569 ms 42688 KB Output is correct
55 Correct 201 ms 26936 KB Output is correct
56 Correct 378 ms 55148 KB Output is correct
57 Correct 387 ms 27540 KB Output is correct
58 Correct 512 ms 28112 KB Output is correct
59 Correct 270 ms 53528 KB Output is correct