oj.uz

Submission #1016136

# Submission time Handle Problem Language Result Execution time Memory
1016136 2024-07-07T12:33:16 Z vjudge1 Meteors (POI11_met) C++17
74 / 100
 2332 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 3e5 + 2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int off = (1 << 19);
struct sgt{
	int val[MAXN * 12], rs[MAXN * 12], ls[MAXN * 12], head = 1;
	int version[MAXN];
	int my_new(int u = 0){
		val[head] = val[u];
		ls[head] = ls[u];
		rs[head] = rs[u];
		return head++;
	}
	int update(int l, int r, int v, int u, int lo = 0, int hi = off){
		if (r <= lo || hi <= l)
			return u;
		u = my_new(u);
		if (l <= lo && hi <= r){
			val[u] += v;
			ckmin(val[u], int(1e9));
			return u;
		}
		int mi = (lo + hi) >> 1;
		ls[u] = update(l, r, v, ls[u], lo, mi);
		rs[u] = update(l, r, v, rs[u], mi, hi);
		return u;
	}
	void query(int l, int r, int v, int cur){
		if (l <= r){
			version[cur] = update(l, r + 1, v, version[cur - 1]);
		} else {
			version[cur] = update(l, off, v, version[cur - 1]);
			version[cur] = update(0, r + 1, v, version[cur]);
		}
	}
	int get(int pos, int u, int lo = 0, int hi = off){
		if (pos >= hi || pos < lo)
			return 0;
		if (!u) return 0;
		int mi = (lo + hi) >> 1;
		if (pos < mi)
			return val[u] + get(pos, ls[u], lo, mi);
		else
			return val[u] + get(pos, rs[u], mi, hi);
	}
} seg;
struct postions {
	int head[MAXN], next[MAXN], val[MAXN], tot = 1;
	void add(int num, int pos){
		next[tot] = head[num];
		val[tot] = pos;
		head[num] = tot;
		tot++;
	}
} pos;
int need[MAXN];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x; 
		cin >> x;
		pos.add(x, i);
	}
	for (int i = 1; i <= n; i++){
		cin >> need[i];
	}
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++){
		int l, r, v;
		cin >> l >> r >> v;
		seg.query(l, r, v, i);
	}
	for (int i = 1; i <= n; i++){
		int lo = 0, hi = q + 1;
		while (hi - lo > 1){
			int mi = (lo + hi) >> 1;
			int sum = 0;
			for (int idx = pos.head[i]; idx; idx = pos.next[idx]){
				int cur = pos.val[idx];
				sum += seg.get(cur, seg.version[mi]);
				ckmin(sum, int(1e9));
			}
			if (sum >= need[i])
				hi = mi;
			else 
				lo = mi;
		}
		if (hi != q + 1)
			cout << hi << endl;
		else
			cout << "NIE\n";
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 30728 KB Output is correct
2 Correct 125 ms 36164 KB Output is correct
3 Correct 121 ms 31316 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 33360 KB Output is correct
2 Correct 98 ms 33364 KB Output is correct
3 Correct 109 ms 35920 KB Output is correct
4 Correct 26 ms 9564 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35164 KB Output is correct
2 Correct 57 ms 34644 KB Output is correct
3 Correct 25 ms 29776 KB Output is correct
4 Correct 85 ms 31572 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 35920 KB Output is correct
2 Correct 71 ms 35920 KB Output is correct
3 Correct 61 ms 31316 KB Output is correct
4 Correct 113 ms 34196 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2332 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2164 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -