oj.uz

Submission #54289

# Submission time Handle Problem Language Result Execution time Memory
54289 2018-07-03T05:50:16 Z 윤교준(#1474) Sails (IOI07_sails) C++11
0 / 100
 1000 ms 8140 KB 
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define revv(V) reverse(allv(V))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 100005;
const int MX = 131072;

struct SEG {
    SEG() { init(); }
	int d[MAXN*3], di[MAXN*3];
	void init(int i, int s, int e) {
		di[i] = e;
		if(s == e) return;
		int m = (s+e)/2;
		init(i*2, s, m); init(i*2+1, m+1, e);
	}
	void init() {
		init(1, 1, 100000);
	}
	void upd(int i, int s, int e, int x, int r) {
		if(x < s || e < x) return;
		if(s == e) {
			d[i] = r;
			return;
		}
		int m = (s+e)/2;
		upd(i*2, s, m, x, r);
		upd(i*2+1, m+1, e, x, r);

		if(d[i*2] < d[i*2+1]) {
			d[i] = d[i*2];
			di[i] = di[i*2];
		} else {
			d[i] = d[i*2+1];
			di[i] = di[i*2+1];
		}
	}
	void upd(int x, int r) { upd(1, 1, 100000, x, r); }
	pii get(int i, int s, int e, int p, int q) {
		if(q < p || e < p || q < s) return pii(INF, -1);
		if(p <= s && e <= q) return pii(d[i], di[i]);
		int m = (s+e)/2;
		pii l = get(i*2, s, m, p, q), r = get(i*2+1, m+1, e, p, q);
        if(l.first < r.first) return l;
        return r;
	}
	pii get(int p, int q) { return get(1, 1, 100000, p, q); }
} seg;

int C[MAXN];
int A[MAXN], B[MAXN];

ll Ans;
int N;

int main() {
    //freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];

	for(int i = 1; i <= N; i++) {
		for(int t = 0; t < B[i]; t++) {
			pii ret = seg.get(1, A[i]);
			ret.first++;
			C[ret.second] = ret.first;
			seg.upd(ret.second, ret.first);
			//printf("%d %d : %d %d\n", i, t, ret.first, ret.second);
		}
	}

	for(int i = 1; i <= 100000; i++) {
		Ans += ll(C[i]) * (C[i]-1) / 2;
	}

	cout << Ans << endl;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 4 ms 1580 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 916 ms 1888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 2380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 2904 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 3892 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 5720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 6832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 8140 KB Time limit exceeded
2 Halted 0 ms 0 KB -