oj.uz

답안 #865406

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865406 2023-10-24T08:00:43 Z Nuraly_Serikbay Meteors (POI11_met) C++17
87 / 100
 3125 ms 65536 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),cout.tie(0)
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
 
const int N = 3e5 + 15;
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], ans[N];
pair <int, int> brd[N];
vector <int> pos[N], MID[N];
long long t[N*4], mod[N*4];
 
void upd (int v, int tl, int tr, int ql, int qr, int val) {
	if (tr < ql || qr < tl) return;
	if (ql <= tl && tr <= qr) {
		t[v] += val;
		return;
	}
	int mid = (tl + tr) >> 1;
	upd (v + v, tl, mid, ql, qr, val), upd (v + v + 1, mid + 1, tr, ql, qr, val);
	return; 
}
 
long long get (int v, int tl, int tr, int pos) {
	if (tl == tr) return t[v];
	int mid = (tl + tr) >> 1;
	if (pos <= mid) return (t[v] + get (v + v, tl, mid, pos));
	return (t[v] + get (v + v + 1, mid + 1, tr, pos));
}
 
void cl (int v, int tl, int tr) {
	t[v] = 0;
	if (tl == tr) return;
	int mid = (tl + tr) >> 1;
	cl (v + v, tl, mid), cl (v + v + 1, mid + 1, tr);
	return;
}
 
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) brd[i] = make_pair (1, q + 1);
	long long sum = 0, ok = 1;
	while (ok) {
		ok = 0;
		for (int i = 1; i <= n; ++ i) {
			if (brd[i].F >= brd[i].S) continue;
			MID[(brd[i].F + brd[i].S) >> 1].pb (i);
		}
		
		for (int mid = 1; mid <= q; ++ mid) {
			if (l[mid] <= r[mid]) upd (1, 1, m, l[mid], r[mid], a[mid]);
			else {
				upd (1, 1, m, 1, r[mid], a[mid]);
				upd (1, 1, m, l[mid], m, a[mid]);
			}
			for (auto i: MID[mid]) {
				sum = 0, ok = 1;
				for (auto j: pos[i]) {
					sum += get (1, 1, m, j);
					if (sum >= p[i]) break;
				}
				if (sum >= p[i]) brd[i].S = mid;
				else brd[i].F = mid + 1;
			}
			MID[mid].clear();
		}
		memset (t, 0, sizeof(t));
	}	
	for (int i = 1; i <= n; ++ i) {
		if (brd[i].S == q + 1) cout << "NIE\n";
		else cout << brd[i].S << '\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;
}

Compilation message

met.cpp:16:22: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   16 | const int INF = 2e18 + 1;
      |                 ~~~~~^~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 9 ms 31280 KB Output is correct
3 Correct 9 ms 31068 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 31068 KB Output is correct
2 Correct 8 ms 31068 KB Output is correct
3 Correct 10 ms 31336 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 31920 KB Output is correct
2 Correct 306 ms 35796 KB Output is correct
3 Correct 308 ms 33548 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 32848 KB Output is correct
2 Correct 276 ms 32892 KB Output is correct
3 Correct 278 ms 35764 KB Output is correct
4 Correct 57 ms 32836 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 32272 KB Output is correct
2 Correct 183 ms 36308 KB Output is correct
3 Correct 131 ms 31312 KB Output is correct
4 Correct 287 ms 33876 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 31572 KB Output is correct
2 Correct 238 ms 33044 KB Output is correct
3 Correct 256 ms 31820 KB Output is correct
4 Correct 299 ms 36944 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2535 ms 46552 KB Output is correct
2 Correct 1032 ms 33608 KB Output is correct
3 Correct 693 ms 31644 KB Output is correct
4 Correct 3125 ms 65536 KB Output is correct

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2477 ms 45660 KB Output is correct
2 Correct 730 ms 33740 KB Output is correct
3 Correct 566 ms 31260 KB Output is correct
4 Runtime error 2642 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -