Submission #870181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870181	2023-11-07T07:12:07 Z	vjudge1	Meteors (POI11_met)	C++17	100 / 100	3521 ms	65536 KB

// KCPC - 50.6907
#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define md(l, r) ((l + r) >> 1)
#define rv(x) ((x << 1) + 1)
#define lv(x) (x << 1)
#define pb emplace_back
#define elif else if
#define uns unsigned
#define emp empty()
#define nll nullptr
#define S second
#define F first

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef pair < ll, ll > pll;
typedef pair < int, int > pi;
typedef pair < ldb, ldb > pldb;
typedef vector < pair < ll, ll > > vpll;
typedef vector < pair < int, int > > vpi;

const int N = 3e5 + 3;
const int M = 1e4 + 123;
const int mod = 1e9 + 7;
const int mxlg = 19;
const int K = 20;
const int P = 31;
const ll inf = 1e9 + 10;

//mt19937 rnd(07062006);

int n, m, q;
int a[N], l[N], r[N], x[N];
int al[N], ar[N];

ll s;
ll t[4 * N];

vi v[N], vq[N];

void upd(int tl, int tr, int x, int v = 1, int l = 1, int r = m){
	if(r < tl || tr < l) return;
	if(tl <= l && r <= tr){
		t[v] += x;
		return;
	}
	ll m = md(l, r);
	upd(tl, tr, x, lv(v), l, m);
	upd(tl, tr, x, rv(v), m + 1, r);
}

ll get(int k, int v = 1, int l = 1, int r = m){
	if(l == r) return t[v];
	ll m = md(l, r);
	if(k <= m) return get(k, lv(v), l, m) + t[v]; 
	else return get(k, rv(v), m + 1, r) + t[v];
}

void output(){
	cin >> n >> m;
	for(int i = 1, b; i <= m; i++) cin >> b, v[b].pb(i);
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> q;
	for(int i = 1; i <= n; i++) al[i] = 1, ar[i] = q + 1;
	for(int i = 1; i <= q; i++) cin >> l[i] >> r[i] >> x[i];
	bool ok = 1;
	while(ok){
		ok = 0;
		memset(t, 0, sizeof(t));
		for(int i = 1; i <= n; i++)
			if(al[i] != ar[i])
				vq[md(al[i], ar[i])].pb(i);
		for(int i = 1; i <= q; i++){
			if(l[i] <= r[i]) upd(l[i], r[i], x[i]);
			else upd(l[i], m, x[i]), upd(1, r[i], x[i]);
			for(auto id : vq[i]){
				ok = 1, s = 0;
				for(auto x : v[id]){
					s += get(x);
					if(s >= a[id]) break;
				}
				if(s >= a[id]) ar[id] = i;
				else al[id] = i + 1;
			}
			vq[i].clear();
		}
	}
	for(int i = 1; i <= n; i++){
		if(al[i] == q + 1) cout << "NIE\n";
		else cout << al[i] << '\n';
	}
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
//      cout << "Case " << i << ":\n";
        output();
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	229 ms	29996 KB	Output is correct
2	Correct	318 ms	31816 KB	Output is correct
3	Correct	294 ms	31568 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	284 ms	30976 KB	Output is correct
2	Correct	294 ms	30920 KB	Output is correct
3	Correct	294 ms	31864 KB	Output is correct
4	Correct	64 ms	30868 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	30544 KB	Output is correct
2	Correct	195 ms	32548 KB	Output is correct
3	Correct	145 ms	29520 KB	Output is correct
4	Correct	321 ms	31816 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	253 ms	29532 KB	Output is correct
2	Correct	246 ms	31012 KB	Output is correct
3	Correct	255 ms	29836 KB	Output is correct
4	Correct	308 ms	33104 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2599 ms	42708 KB	Output is correct
2	Correct	1024 ms	31132 KB	Output is correct
3	Correct	685 ms	29632 KB	Output is correct
4	Correct	3521 ms	62992 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2642 ms	41500 KB	Output is correct
2	Correct	750 ms	31124 KB	Output is correct
3	Correct	548 ms	29276 KB	Output is correct
4	Correct	3286 ms	65536 KB	Output is correct

Submission #870181

Compilation message