oj.uz

답안 #583146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583146 2022-06-24T22:22:59 Z Shreyan_Paliwal Sails (IOI07_sails) C++17
10 / 100
 298 ms 3112 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000;
const int segn = (1<<18);

int n;

pair<int,int> masts[maxn];

int seg[segn];
int flg[segn];

void push(int p, int l, int r) {
	if (l == r) {flg[p] = 0; return;}
	if (flg[p] == 0) return;
	seg[2*p] += flg[p]; flg[2*p] += flg[p];
	seg[2*p+1] += flg[p]; flg[2*p+1] += flg[p];
	flg[p] = 0;
}

void upd(int p, int l, int r, int L, int R) {
	push(p, l, r);
	if (R < l || r < L) return;
	if (L <= l && r <= R) {
		seg[p]++; flg[p]++;
		return;
	}
	int mid = (l + r)/2;
	upd(2*p, l, mid, L, R); upd(2*p+1, mid+1, r, L, R);
	seg[p] = max(seg[2*p], seg[2*p + 1]);
}

int qry(int p, int l, int r, int L, int R) {
	push(p, l, r);
	if (R < l || r < L) return -1;
	if (L <= l && r <= R) return seg[p];
	int mid = (l + r)/2;
	return max(qry(2*p, l, mid, L, R), qry(2*p+1, mid+1, r, L, R));
}

int fl(int p, int l, int r, int v) {
	push(p, l, r);
	if (l == r) return l + (seg[p] != v);
	int mid = (l + r) >> 1;
	if (seg[2*p + 1] <= v) return fl(2*p, l, mid, v);
	else return fl(2*p + 1, mid+1, r, v);
}

int fr(int p, int l, int r, int v) {
	push(p, l, r);
	if (l == r) return l;
	int mid = (l + r) >> 1;
	if (seg[2*p + 1] < v) return fr(2*p, l, mid, v);
	else return fr(2*p+1, mid+1, r, v);
}


int main() {
	cin >> n;

	for (int i = 0; i < n; i++) cin >> masts[i].first >> masts[i].second;

	sort(masts, masts + n);

	for (int i = 0; i < n; i++) {
		int ht = masts[i].first, k = masts[i].second;
		int maxv = qry(1, 0, n-1, ht-k, ht);
		int l = fl(1, 0, n-1, maxv), r = fr(1, 0, n-1, maxv);
		int numright = (ht - 1) - r;
		if (numright <= 0) 
			upd(1, 0, n-1, l, l + k - 1);
		  // {upd(1, 0, n-1, l, l + k - 1); cout << l << " " << l + k - 1 << endl; }
		else {
			// cout << r + 1 << " " << ht - 1 << " " << l << " " << l + (k - numright) -1 << endl;
			upd(1, 0, n-1, r + 1, ht - 1);
			upd(1, 0, n-1, l, l + (k - numright) - 1);
		}
	}

	long long ans = 0;
	for (int i = 0; i < 100000; i++) {
		long long x = qry(1, 0, n-1, i, i);
		ans += (long long)(x * (x - 1) / 2);
	}

	cout << ans << '\n';

	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 1024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 175 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 159 ms 2928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 222 ms 2928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 3112 KB Output is correct
2 Correct 198 ms 2200 KB Output is correct