Submission #1016138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016138		vjudge1	Meteors (POI11_met)	C++17	74 / 100	309 ms	46928 KiB

met

#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 << 16);
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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13