oj.uz

Submission #835283

# Submission time Handle Problem Language Result Execution time Memory
835283 2023-08-23T11:40:55 Z Valaki2 Horses (IOI15_horses) C++14
17 / 100
 517 ms 61196 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int mod = 1e9 + 7;
const int maxn = 5e5;
const int maxy = 1e9;

int add(int a, int b) {
	return (a + b) % mod;
}

int subt(int a, int b) {
	return (a - b + mod) % mod;
}

int mult(int a, int b) {
	return (a * b) % mod;
}

int power(int a, int b) {
	if(b == 0) {
		return 1ll;
	}
	if(b % 2 == 0) {
		int part = power(a, b / 2);
		return mult(part, part);
	} else {
		return mult(a, power(a, b / 2));
	}
}

int inv(int a) {
	return power(a, mod - 2);
}

int divi(int a, int b) {
	return mult(a, inv(b));
}

int n;
int x[1 + maxn], y[1 + maxn];
set<int> big/*s*/;

int tree[1 + maxn];
int segtree[1 + 4 * maxn];

void upd(int pos, int val) {
	while(pos <= n) {
		tree[pos] = mult(tree[pos], val);
		pos += pos & (-pos);
	}
}

int qry(int pos) {
	int res = 1;
	while(pos > 0) {
		res = mult(res, tree[pos]);
		pos -= pos & (-pos);
	}
	return res;
}

void upd_maxi(int v, int vl, int vr, int pos, int val) {
	if(vl == vr) {
		segtree[v] = val;
	} else {
		int mid = (vl + vr) / 2;
		if(pos <= mid) {
			upd_maxi(2 * v, vl, mid, pos, val);
		} else {
			upd_maxi(2 * v + 1, mid + 1, vr, pos, val);
		}
		segtree[v] = max(segtree[2 * v], segtree[2 * v + 1]);
	}
}

int qry_maxi(int v, int vl, int vr, int ql, int qr) {
	if(ql > vr || qr < vl) {
		return 1;
	}
	if(ql == vl && qr == vr) {
		return segtree[v];
	}
	int mid = (vl + vr) / 2;
	return max(qry_maxi(2 * v, vl, mid, ql, min(qr, mid)),
			qry_maxi(2 * v + 1, mid + 1, vr, max(ql, mid + 1), qr));
}

int calc() {
	int cur_factor = 1, all_factor = 1;
	int prev = n + 1;
	int ans = 0, best = 0;
	for(auto it = big.rbegin(); it != big.rend(); it++) {
		int cur = *it;
		int cur_best_y = qry_maxi(1, 1, n, cur, prev - 1);
		if(cur_best_y > best * cur_factor) {
			best = cur_best_y;
			int cur_pref_x = qry(cur);
			ans = mult(cur_pref_x, cur_best_y);
			cur_factor = 1;
		}
		cur_factor *= x[cur];
		all_factor *= x[cur];
		if(all_factor > maxy) {
			break;
		}
		prev = cur;
	}
	return ans;
}

signed init(signed N, signed X[], signed Y[]) {
	n = N;
	x[0] = y[0] = 1;
	for(int i = 1; i <= n; i++) {
		x[i] = X[i - 1];
		y[i] = Y[i - 1];
	}
	tree[0] = 1;
	for(int i = 1; i <= n; i++) {
		tree[i] = 1;
	}
	for(int i = 1; i <= n; i++) {
		upd(i, x[i]);
		upd_maxi(1, 1, n, i, y[i]);
	}
	for(int i = 1; i <= n; i++) {
		if(x[i] > 1) {
			big.insert(i);
		}
	}
	big.insert(1);
	return calc();
}

signed updateX(signed pos, signed val) {
	pos++;
	int where = pos, newval = val;
	upd(where, divi(newval, x[where]));
	if(x[where] == 1 && newval > 1) {
		big.insert(where);
	}
	if(x[where] > 1 && newval == 1) {
		big.erase(where);
	}
	big.insert(1);
	x[where] = newval;
	return calc();
}

signed updateY(signed pos, signed val) {
	pos++;
	int where = pos, newval = val;
	y[where] = newval;
	upd_maxi(1, 1, n, where, newval);
	return calc();
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:141:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:156:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  156 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:164:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  164 |  return calc();
      |         ~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 316 KB Output is correct
12 Correct 1 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 1 ms 340 KB Output is correct
19 Correct 0 ms 340 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 0 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 0 ms 320 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 1 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 1 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 316 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 312 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 52416 KB Output is correct
2 Incorrect 276 ms 61196 KB Output isn't correct
3 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 0 ms 284 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 308 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 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 340 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 316 KB Output is correct
16 Correct 1 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 Incorrect 0 ms 212 KB Output isn't correct
22 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 368 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 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 320 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 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 0 ms 316 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 Incorrect 0 ms 316 KB Output isn't correct
22 Halted 0 ms 0 KB -