oj.uz

Submission #875949

# Submission time Handle Problem Language Result Execution time Memory
875949 2023-11-20T20:32:40 Z Lobo Boat (APIO16_boat) C++17
0 / 100
 2000 ms 301556 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
const int maxn = 1e6+10;
const int maxv = 1e9;
const int lg = 31;
const int mod = 1e9+7;

int n;
int lc[maxn*lg], rc[maxn*lg], tr[maxn*lg], cntno;

int upd(int no, int l, int r, int pos, int val) {
	if(l > pos or r < pos) return no;
	if(no == 0) no = ++cntno;
	if(l == r) {
		tr[no]+= val;
		return no;
	}
	int mid = (l+r)/2;

	lc[no] = upd(lc[no],l,mid,pos,val);
	rc[no] = upd(rc[no],mid+1,r,pos,val);
	tr[no] = tr[lc[no]]+tr[rc[no]];
	return no;
}

int query(int no, int l, int r, int ll, int rr) {
	if(l > rr or r < ll or no == 0) return 0;
	if(l >= ll && r <= rr) return tr[no];
	int mid = (l+r)/2;
	return query(lc[no],l,mid,ll,rr)+query(rc[no],mid+1,r,ll,rr);
}

int32_t main() {
	cin >> n;

	int rt = upd(0,0,maxv,0,1);
	for(int i = 1; i <= n; i++) {
		int a,b; cin >> a >> b;
		for(int j = b; j >= a; j--) {
			upd(rt,0,maxv,j,query(rt,0,maxv,0,j-1));
		}
	}

	cout << query(rt,0,maxv,1,maxv) << endl;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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