Submission #361531

#	Time	Username	Problem	Language	Result	Execution time	Memory
361531		pure_mem	Sails (IOI07_sails)	C++14	100 / 100	977 ms	3220 KiB

sails

#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;

inline 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;
}

inline 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]);
}

inline 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));
}

inline 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;
}

inline 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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10