oj.uz

답안 #865198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865198 2023-10-24T06:28:50 Z Nuraly_Serikbay Meteors (POI11_met) C++17
24 / 100
 6000 ms 48984 KB 
//çalışan kazanır//
 
#include "bits/stdc++.h"
 
using namespace std;
 
#define int long long
#define pb push_back
#define S second
#define F first
#define all(x) x.begin(),x.end()
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
 
const int N = 4e5 + 1;
const int INF = 2e18 + 1;
const int MOD = 1e9 + 7;
const int MODD = 1070234587ll;
const double eps = 0.0001;
//const int p = 87;

int n, m, o[N], p[N], q, l[N], r[N], a[N];
vector <int> pos[N];
int t[N*4], mod[N*4];

void push (int v, int tl, int tr) {
	if (mod[v] && tl != tr) {
		mod[v + v] += mod[v], mod[v + v + 1] += mod[v];
		t[v + v] += mod[v], t[v + v + 1] += mod[v];
		mod[v] = 0;
	}
	return;
}

void upd (int v, int tl, int tr, int l, int r, int val) {
	push (v, tl, tr);
	if (tr < l || r < tl) return;
	if (l <= tl && tr <= r) {
		t[v] += val;
		mod[v] += val;
		push (v, tl, tr);
		return;
	}
	int mid = (tl + tr) >> 1;
	upd (v + v, tl, mid, l, r, val), upd (v + v + 1, mid + 1, tr, l, r, val);
	t[v] = max (t[v + v], t[v + v + 1]);
	return; 
}

void cl (int v, int tl, int tr) {
	t[v] = mod[v] = 0; 
	if (tl == tr) return;
	int mid = (tl + tr) >> 1;
	cl (v + v, tl, mid), cl (v + v + 1, mid + 1, tr);
	return;
}

int get (int v, int tl, int tr, int pos) {
	push (v, tl, tr);
	if (tl == tr) return t[v];
	int mid = (tl + tr) >> 1;
	if (pos <= mid) return get (v + v, tl, mid, pos);
	return get (v + v + 1, mid + 1, tr, pos);
}

int check (int x, int idx) {
	for (int i = 1; i <= x; ++ i) {
		if (l[i] <= r[i]) upd (1, 1, m, l[i], r[i], a[i]);
		else upd (1, 1, m, 1, r[i], a[i]), upd (1, 1, m, l[i], m, a[i]);
	}
	int sum = 0;
	for (auto i: pos[idx]) {
	//	cout << i << " --> " << get (1, 1, m, i) << '\n';
		sum += get (1, 1, m, i);
	}
	cl(1, 1, m);
//	cout << x << ' ' << idx << " ==> " << sum << ' ' << p[idx] << '\n';
	return (sum >= p[idx]);
}

void solution () {	
	cin >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		cin >> o[i];
		pos[o[i]].pb (i);
	}
	for (int i = 1; i <= n; ++ i) cin >> p[i];
	cin >> q;
	for (int i = 1; i <= q; ++ i) cin >> l[i] >> r[i] >> a[i];
	
	
	for (int i = 1; i <= n; ++ i) {
		int L = 0, R = q, rs = -1;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (check (mid, i)) R = mid - 1, rs = mid;
			else L = mid + 1;
		}
		if (rs == -1) cout << "NIE\n";
		else cout << rs << '\n';
		
	}
	
	
	return;
}
 
signed main() {
	YOSIK();
//	srand (time(0));
//	freopen ("E.in", "r", stdin);
//	freopen ("E.out", "w", stdout);
	int TT = 1;// cin >> TT;
	for (int i = 1; i <= TT; ++ i) {
//		cout << "Case " << i << ": ";
		solution ();
		
  	}
 
	return 0;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 20996 KB Output is correct
2 Correct 1239 ms 20992 KB Output is correct
3 Correct 324 ms 20992 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 251 ms 20992 KB Output is correct
2 Correct 109 ms 21000 KB Output is correct
3 Correct 1345 ms 21076 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6013 ms 22360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6012 ms 23640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6053 ms 22616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6019 ms 22488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6015 ms 48984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6006 ms 48708 KB Time limit exceeded
2 Halted 0 ms 0 KB -