oj.uz

Submission #54292

# Submission time Handle Problem Language Result Execution time Memory
54292 2018-07-03T06:03:26 Z 윤교준(#1474) Sails (IOI07_sails) C++11
30 / 100
 1000 ms 4428 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] = 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;

	{
	    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 4 ms 1400 KB Output is correct
2 Correct 3 ms 1512 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1696 KB Output is correct
2 Correct 5 ms 1720 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1720 KB Output is correct
2 Correct 63 ms 1720 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 1944 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 1072 ms 2172 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 1088 ms 2352 KB Time limit exceeded

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 4428 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 1083 ms 4428 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 1086 ms 4428 KB Time limit exceeded
2 Halted 0 ms 0 KB -