제출 #361528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361528		pure_mem	Sails (IOI07_sails)	C++17	30 / 100	1099 ms	2964 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;

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 dval = get(1, 1, m, tr, tr);
	while(tl <= tr){
		int tm = (tl + tr) / 2;
		if(get(1, 1, m, tm, tm) == dval)
			tr = tm - 1;
		else
			tl = tm + 1;
	}
	return tr + 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++){			
		while(a[i].Y > 0){
			int pos = get_f(1, a[i].X);	
			upd(1, 1, m, pos, min(pos + a[i].Y - 1, a[i].X));
			//cerr << i << " " << pos << " " << min(pos + a[i].Y - 1, a[i].X) << "\n";
			a[i].Y -= min(pos + a[i].Y - 1, a[i].X) - pos + 1;
			a[i].X = pos - 1;
		}
	}	
	for(int i = 1;i <= m;i++){
		ll x = get(1, 1, m, i, i);
		ans += x * (x - 1) / 2;
		//cerr << i << " " << x << "\n";
	}
	printf("%lld", ans);	
}

컴파일 시 표준 에러 (stderr) 메시지

sails.cpp: In function 'int main()':
sails.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
sails.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   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: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10