oj.uz

Submission #54293

# Submission time Handle Problem Language Result Execution time Memory
54293 2018-07-03T06:05:35 Z 윤교준(#1474) Sails (IOI07_sails) C++11
30 / 100
 1000 ms 4288 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#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] = s;
		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;
		return min(get(i*2, s, m, p, q), get(i*2+1, m+1, e, p, q));
	}
	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;

	{
	    vector<pii> V;
	    for(int i = 1, a, b; i <= N; i++) {
            cin >> a >> b;
            V.eb(a, b);
	    }
	    sorv(V);
        for(int i = 0; i < N; i++)
            tie(A[i+1], B[i+1]) = V[i];
	}

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

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 4 ms 1512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1512 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1628 KB Output is correct
2 Correct 77 ms 1644 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 2060 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 1073 ms 2192 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 2464 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 4288 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 1079 ms 4288 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 1091 ms 4288 KB Time limit exceeded
2 Halted 0 ms 0 KB -