oj.uz

Submission #869915

# Submission time Handle Problem Language Result Execution time Memory
869915 2023-11-06T10:16:32 Z qin Horses (IOI15_horses) C++17
17 / 100
 160 ms 69136 KB 
#ifdef LOCAL
#else
#include "horses.h"
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double db;
int inf = 2e09; ll infll = 2e18; ll mod = 1e09+7;
vector<ll> X, Y; // UWAGA - GLOBALNIE ZADEKLAROWANE
int base = 1;
struct seg{
		struct Node{
				int opt; ll mul, mulp, muls; bool o, op, os;
				Node() : opt(0), mul(1), mulp(1), muls(1), o(0), op(0), os(0) {}
		};
		vector<Node> t;
		ll mulTmp; bool ovTmp; db proportionTmp;
		void merge(int i){
				t[i].mul = t[i<<1].mul*t[i<<1|1].mul; t[i].o = t[i].mul >= mod ? 1 : t[i].o, t[i].mul %= mod;
				mulTmp = t[i<<1].muls*t[i<<1|1].mulp; ovTmp = mulTmp >= mod ? 1 : 0, mulTmp %= mod;
				if(!Y[t[i<<1|1].opt]) proportionTmp = -1;
				else proportionTmp = db(Y[t[i<<1].opt])/db(Y[t[i<<1|1].opt]);
				if((db(mulTmp) >= proportionTmp || ovTmp) && proportionTmp != -1){ //zwycieża późniejszy
						t[i].opt = t[i<<1|1].opt; 
						t[i].mulp = t[i<<1].mul*t[i<<1|1].mulp, t[i].op = t[i].mulp >= mod ? 1 : t[i].op, t[i].mulp %= mod;
						t[i].muls = t[i<<1|1].muls, t[i].os = t[i<<1|1].os;
				}
				else{ // zwycięża wcześniejszy
						t[i].opt = t[i<<1].opt; 
						t[i].muls = t[i<<1].muls*t[i<<1|1].mul, t[i].os = t[i].muls >= mod ? 1 : t[i].os, t[i].muls %= mod;
						t[i].mulp = t[i<<1].mulp, t[i].op = t[i<<1].op;
				}
		}
		void init(int n){
				while(base < n) base <<= 1;
				t.resize(base<<1);
				X.resize(base+1); Y.resize(base+1);
				//printf("%d\n", base);
				for(int i = 1; i <= n; ++i) t[i+base-1].opt = i, t[i+base-1].mul = X[i], t[i+base-1].mulp = X[i], t[i+base-1].muls = 1; //muls daje na 1, bo miedzy elementami obchodzi mnie tylko przedzial pomiedzy nimi
				for(int i = n+1; i <= base; ++i) X[i] = 1, Y[i] = 0, t[i+base-1].opt = i, t[i+base-1].mul = X[i], t[i+base-1].mulp = X[i], t[i+base-1].muls = 1;
				//exit(0);
				for(int i = base-1; i; --i) merge(i);
				
		}
		void update(int i){
				t[i+base-1].mul = X[i], t[i+base-1].mulp = X[i], t[i+base-1].muls = 1;
				for(i += base-1, i >>= 1; i; i >>= 1) merge(i);
		}
		int query(){ return int(Y[t[1].opt]*t[1].mulp % mod); }
		void print(){
				for(int i = 1; i < base<<1; ++i) printf("%d: %d, %lld %lld %lld\n", i, t[i].opt, t[i].mul, t[i].mulp, t[i].muls);
		}
} seg;
int updateX(int i, int val){ X[i+1] = val; seg.update(i+1); return seg.query(); }
int updateY(int i, int val){ Y[i+1] = val; seg.update(i+1); return seg.query(); }
int init(int n, int x[], int y[]){
		X.resize(n+1), Y.resize(n+1);
		for(int i = 1; i <= n; ++i) X[i] = x[i-1], Y[i] = y[i-1];
		seg.init(n);
		//seg.print();
		return seg.query();
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ){
				int n = 3, x[3] = {2, 1, 3}, y[3] = {3, 2, 1};
				printf("%d\n", init(n, x, y));
		}
		return 0;
}
#endif

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 59928 KB Output is correct
2 Correct 160 ms 69136 KB Output is correct
3 Incorrect 107 ms 61196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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