oj.uz

Submission #599096

# Submission time Handle Problem Language Result Execution time Memory
599096 2022-07-19T10:03:18 Z sofapuden Horses (IOI15_horses) C++14
17 / 100
 246 ms 133488 KB 
#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

typedef long long ll;

const ll M = 1e9+7;

struct seg2 {
	struct nod {
		ll val;
		ll val2;
	};
	int n;
	vector<nod> st;
	vector<ll> A;

	seg2() {}
	seg2(int sz) : n(sz), st(4*n) {}
	seg2(vector<ll> &in) : seg2((int)in.size()) {
		A = in;
		build(0,n-1,1);
	}

	nod merge (nod a, nod b) {
		nod c;
		c.val = min(1ll<<30,a.val)*min(1ll<<30,b.val);
		c.val2 = a.val2*b.val2%M;
		return c;
	}
	
	void build(int l, int r, int p){
		if(l == r){
			nod c;
			c.val = A[l];
			c.val2 = A[l];
			st[p] = c;
			return;
		}
		int m = (l+r) >> 1;
		build(l,m,p<<1);
		build(m+1,r,p<<1|1);
		st[p] = merge(st[p<<1],st[p<<1|1]);
	}

	void update(int x, ll val, int l, int r, int p){
		if(l == r){
			nod c;
			c.val = val;
			c.val2 = val;
			st[p] = c;
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)update(x,val,l,m,p<<1);
		else update(x,val,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}
	void updateno(int x, int l, int r, int p){
		if(l == r){
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)updateno(x,l,m,p<<1);
		else updateno(x,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}

	nod que(int i, int j, int l, int r, int p){
		if(l >= i && r <= j)return st[p];
		int m = (l+r)>>1;
		if(m < i)return que(i,j,m+1,r,p<<1|1);
		else if(m >= j)return que(i,j,l,m,p<<1);
		else return merge(que(i,j,l,m,p<<1),que(i,j,m+1,r,p<<1|1));
	}
}st2;

struct seg {
	struct nod {
		int pos;
	};
	int n;
	vector<nod> st;
	vector<ll> Ax;
	vector<ll> Ay;
	seg2 stval;

	seg() {}
	seg(int sz) : n(sz), st(4*n) {}
	seg(vector<ll> &_X, vector<ll> &_Y, seg2 _stval) : seg((int)_X.size()) {
		Ax = _X;
		Ay = _Y;
		stval = _stval;
		build(0,n-1,1);
	}

	nod merge (nod a, nod b) {
		ll v1 = stval.que(a.pos+1,b.pos,0,n-1,1).val*Ay[b.pos];
		ll v2 = Ay[a.pos];
		if(v1 > v2)return b;
		else return a;
	}
	
	void build(int l, int r, int p){
		if(l == r){
			nod c;
			c.pos = l;
			st[p] = c;
			return;
		}
		int m = (l+r) >> 1;
		build(l,m,p<<1);
		build(m+1,r,p<<1|1);
		st[p] = merge(st[p<<1],st[p<<1|1]);
	}

	void update(int x, ll val, int l, int r, int p){
		if(l == r){
			Ay[l] = val;
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)update(x,val,l,m,p<<1);
		else update(x,val,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}
	void updateno(int x, int l, int r, int p){
		if(l == r){
			return;
		}
		int m = (l+r) >> 1;
		if(m >= x)updateno(x,l,m,p<<1);
		else updateno(x,m+1,r,p<<1|1);
		st[p] = merge(st[p<<1], st[p<<1|1]);
	}

	nod que(int i, int j, int l, int r, int p){
		if(l >= i && r <= j)return st[p];
		int m = (l+r)>>1;
		if(m < i)return que(i,j,m+1,r,p<<1|1);
		else if(m >= j)return que(i,j,l,m,p<<1);
		else return merge(que(i,j,l,m,p<<1),que(i,j,m+1,r,p<<1|1));
	}
}st;

int glN;
vector<ll> x, y;

int init(int N, int X[], int Y[]) {
	glN = N;
	x.resize(N);
	y.resize(N);
	for(int i = 0; i < N; ++i){
		x[i] = X[i];
		y[i] = Y[i];
	}
	st2 = seg2(x);
	st = seg(x,y,st2);
	return (int)(st.stval.que(0,st.st[1].pos,0,glN-1,1).val2*st.Ay[st.st[1].pos]%M);
}

int updateX(int pos, int val) {	
	st.stval.update(pos,val,0,glN-1,1);
	st.updateno(pos,0,glN-1,1);
	return (int)(st.stval.que(0,st.st[1].pos,0,glN-1,1).val2*st.Ay[st.st[1].pos]%M);
}

int updateY(int pos, int val) {
	st.update(pos,val,0,glN-1,1);
	st.stval.updateno(pos,0,glN-1,1);
	return (int)(st.stval.que(0,st.st[1].pos,0,glN-1,1).val2*st.Ay[st.st[1].pos]%M);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 280 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 1 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 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 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 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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 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 Incorrect 2 ms 468 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 246 ms 133488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 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 1 ms 232 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 228 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 212 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 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 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 1 ms 300 KB Output is correct
23 Incorrect 2 ms 568 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 1 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 1 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 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Correct 1 ms 232 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Incorrect 2 ms 568 KB Output isn't correct
24 Halted 0 ms 0 KB -