oj.uz

Submission #743818

# Submission time Handle Problem Language Result Execution time Memory
743818 2023-05-18T03:54:48 Z Abrar_Al_Samit Horses (IOI15_horses) C++17
17 / 100
 1500 ms 92028 KB 
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

const int nax = 5e5 + 2;
const int mod = 1e9 + 7;
const int MX = 1e9;
long long x[nax], y[nax];
int n;

long long mul(long long a, long long b) {
	return (a * b) % mod;
}
long long quickpow(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if(b&1) ret = mul(ret, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ret;
}


struct BIT {
	long long b[nax];
	BIT() {
		for(int i=0; i<nax; ++i) {
			b[i] = 1;
		}
	}

	void update(int p, int val) {
		while(p<nax) {
			b[p] = mul(b[p], val);
			p += p&-p;
		}
	}
	long long query(int p) {
		long long ret = 1;
		while(p) {
			ret = mul(ret, b[p]);
			p -= p&-p;
		}
		return ret;
	}

} fen;
int seg[nax * 4];
void update(int pos, int val, int l=1, int r=n, int v=1) {
	if(l==r) {
		seg[v] = val;
		return;
	}
	int mid = (l+r)/2;
	if(pos<=mid) update(pos, val, l, mid, v*2);
	else update(pos, val, mid+1, r, v*2+1);
	seg[v] = max(seg[v*2], seg[v*2+1]);
}
int query(int L, int R, int l=1, int r=n, int v=1) {
	if(l>=L && r<=R) return seg[v];
	if(l>R || r<L) return 0;
	int mid = (l+r)/2;
	return max(query(L, R, l, mid, v*2), query(L, R, mid+1, r, v*2+1));
}

set<int>nonone;

int mem[nax];
long long get_ans(int day) {
	int sell_max_day;
	auto it = nonone.upper_bound(day);
	if(it==nonone.end()) {
		sell_max_day = n-1;
	} else {
		sell_max_day = *it-1;
	}

	long long price = query(day+1, sell_max_day+1);

	long long cnt = 1;
	bool better = 0;
	for(; it!=nonone.end(); ++it) {
		cnt *= x[*it];

		int then_sell_max_day;
		if(next(it)==nonone.end()) {
			then_sell_max_day = n-1;
		} else {
			then_sell_max_day = *next(it) - 1;
		}

		if(mem[*it]==-1) mem[*it] = query(*it+1, then_sell_max_day+1);
		long long then_price = mem[*it];

		if(cnt * then_price > price) {
			better = true;
			break;
		}
		if(cnt>MX) {
			better = true;
			break;
		}
	}
	if(better) return -1;

	return mul(price, fen.query(day+1));
}
int get() {
	auto it = nonone.end();
	int iter = 30;
	while(iter--) {
		if(it!=nonone.begin()) --it;
		else break;
	}

	if(it==nonone.begin()) {
		long long ans = get_ans(0);
		if(ans!=-1) {
			mem[0] = -1;
			return ans;
		}
	}
	while(it!=nonone.end()) {
		long long ans = get_ans(*it);
		if(ans!=-1) {
			while(it!=nonone.end()) {
				mem[*it] = -1;
				++it;
			}
			return ans;
		}
		mem[*it] = -1;
		++it;
	}


}
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0; i<n; ++i) {
		x[i] = X[i], y[i] = Y[i];
		fen.update(i+1, x[i]);
		update(i+1, y[i]);

		if(x[i]>1) nonone.insert(i);
	}
	memset(mem, -1, sizeof mem);
	return get();
}

int updateX(int pos, int val) {	
	fen.update(pos+1, quickpow(x[pos], mod-2));
	fen.update(pos+1, val);

	if(x[pos]==1 && val>1) {
		nonone.insert(pos);
	} else if(x[pos]>1 && val==1) {
		nonone.erase(pos);
	} 

	x[pos] = val;

	get();
}

int updateY(int pos, int val) {
	update(pos+1, val);
	y[pos] = val;

	get();
}

Compilation message

horses.cpp: In function 'int get()':
horses.cpp:121:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |    return ans;
      |           ^~~
horses.cpp:131:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  131 |    return ans;
      |           ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:143:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  143 |   fen.update(i+1, x[i]);
      |                   ~~~^
horses.cpp:144:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  144 |   update(i+1, y[i]);
      |               ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:153:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  153 |  fen.update(pos+1, quickpow(x[pos], mod-2));
      |                    ~~~~~~~~^~~~~~~~~~~~~~~
horses.cpp:165:1: warning: no return statement in function returning non-void [-Wreturn-type]
  165 | }
      | ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:172:1: warning: no return statement in function returning non-void [-Wreturn-type]
  172 | }
      | ^
horses.cpp: In function 'int get()':
horses.cpp:138:1: warning: control reaches end of non-void function [-Wreturn-type]
  138 | }
      | ^

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6100 KB Output is correct
5 Correct 4 ms 6100 KB Output is correct
6 Correct 3 ms 6100 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 4 ms 6100 KB Output is correct
9 Correct 3 ms 6168 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 2 ms 6100 KB Output is correct
12 Correct 3 ms 6100 KB Output is correct
13 Correct 3 ms 6100 KB Output is correct
14 Correct 3 ms 6100 KB Output is correct
15 Correct 3 ms 6100 KB Output is correct
16 Correct 3 ms 6140 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 6100 KB Output is correct
19 Correct 3 ms 6100 KB Output is correct
20 Correct 4 ms 6108 KB Output is correct
21 Execution timed out 1555 ms 6100 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 232 ms 92028 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6100 KB Output is correct
5 Correct 3 ms 6100 KB Output is correct
6 Correct 3 ms 6100 KB Output is correct
7 Correct 3 ms 6184 KB Output is correct
8 Correct 3 ms 6100 KB Output is correct
9 Correct 4 ms 6100 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 3 ms 6100 KB Output is correct
12 Correct 4 ms 6100 KB Output is correct
13 Correct 3 ms 6100 KB Output is correct
14 Correct 3 ms 6100 KB Output is correct
15 Correct 3 ms 6100 KB Output is correct
16 Correct 3 ms 6100 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 4 ms 6104 KB Output is correct
19 Correct 3 ms 6100 KB Output is correct
20 Correct 3 ms 6120 KB Output is correct
21 Execution timed out 1589 ms 6100 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6100 KB Output is correct
5 Correct 3 ms 6100 KB Output is correct
6 Correct 3 ms 6100 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 3 ms 6100 KB Output is correct
9 Correct 3 ms 6100 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 3 ms 6100 KB Output is correct
12 Correct 3 ms 6100 KB Output is correct
13 Correct 4 ms 6100 KB Output is correct
14 Correct 3 ms 6100 KB Output is correct
15 Correct 3 ms 6100 KB Output is correct
16 Correct 3 ms 6100 KB Output is correct
17 Correct 3 ms 6100 KB Output is correct
18 Correct 3 ms 6100 KB Output is correct
19 Correct 3 ms 6100 KB Output is correct
20 Correct 3 ms 6100 KB Output is correct
21 Execution timed out 1585 ms 6100 KB Time limit exceeded
22 Halted 0 ms 0 KB -