oj.uz

Submission #361529

# Submission time Handle Problem Language Result Execution time Memory
361529 2021-01-30T12:19:23 Z pure_mem Sails (IOI07_sails) C++14
90 / 100
 1000 ms 3820 KB 
#pragma GCC optimize("Ofast")

#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 3;

int t[N * 4], tt[N * 4], m, n;
pair<int, int> a[N];
ll ans;

void push(int v){
	if(!tt[v])
		return;
	tt[v * 2] += tt[v], t[v * 2] += tt[v];
	tt[v * 2 + 1] += tt[v], t[v * 2 + 1] += tt[v];                
	tt[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		tt[v] += 1, t[v] += 1;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r), upd(v * 2 + 1, tm + 1, tr, l, r);
	t[v] = min(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return N;
	if(tl >= l && tr <= r)
		return t[v];
	push(v);
	int tm = (tl + tr) / 2;
	return min(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}

int get_f(int tl, int tr, int pos){
	tr = pos;
	while(tl <= tr){
		int tm = (tl + tr) / 2;
		if(get(1, 1, m, tm, tm) != get(1, 1, m, pos, pos))
			tl = tm + 1;
		else
			tr = tm - 1;
	}
	return tr + 1;
}

int get_s(int tl, int tr, int pos){
	tl = pos;
	while(tl <= tr){
		int tm = (tl + tr) / 2;
		if(get(1, 1, m, tm, tm) == get(1, 1, m, pos, pos))
			tl = tm + 1;
		else
			tr = tm - 1;
	}
	return tl - 1;
}

int main () {
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
		scanf("%d %d", &a[i].X, &a[i].Y), m = max(m, a[i].X);
	sort(a + 1, a + n + 1);
	for(int i = 1;i <= n;i++){			
		int tl = get_f(1, a[i].X, a[i].X - a[i].Y + 1), tr = get_s(1, a[i].X, a[i].X - a[i].Y + 1);
		upd(1, 1, m, tl, tl + (tr - (a[i].X - a[i].Y + 1) + 1) - 1);
		upd(1, 1, m, tr + 1, a[i].X);		
	}	
	for(int i = 1;i <= m;i++){
		ll x = get(1, 1, m, i, i);
		ans += x * (x - 1) / 2;
	}
	printf("%lld", ans);	
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
sails.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d %d", &a[i].X, &a[i].Y), m = max(m, a[i].X);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 364 KB Output is correct
2 Correct 34 ms 2412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 876 KB Output is correct
2 Correct 159 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 1004 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 1900 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 3072 KB Output is correct
2 Correct 899 ms 3820 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 3180 KB Output is correct
2 Correct 563 ms 3692 KB Output is correct

Subtask #11
0 / 10.0

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