oj.uz

Submission #361528

# Submission time Handle Problem Language Result Execution time Memory
361528 2021-01-30T12:09:26 Z pure_mem Sails (IOI07_sails) C++17
30 / 100
 1000 ms 2964 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 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);	
}

Compilation message

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.0 / 5.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 #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 1 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 3 ms 364 KB Output is correct
2 Correct 30 ms 364 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 572 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 1086 ms 888 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 1065 ms 788 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 1004 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 2964 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 1280 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 1042 ms 1540 KB Time limit exceeded
2 Halted 0 ms 0 KB -