oj.uz

Submission #117632

# Submission time Handle Problem Language Result Execution time Memory
117632 2019-06-16T20:52:25 Z KieranHorgan Sails (IOI07_sails) C++17
100 / 100
 66 ms 5124 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 1000000007;


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long seed;
	asm("rdtsc" : "=A"(seed));
	srand(seed);

	int n;
	cin >> n;
	// n=100000;
	int total = 0;
	int mx = 0;
	vector<pair<int,int>> listOfHeights;
	for(int i = 0; i < n; i++) {
		int H, K;
		cin >> H >> K;
		// H=K=min(i+1, 750);
		listOfHeights.push_back({H,K});
	}
	sort(listOfHeights.begin(), listOfHeights.end());
	int differentHeights = 1;
	for(int i = 1; i < n; i++)
		if(listOfHeights[i].first != listOfHeights[i-1].first)
			differentHeights++;


	vector<int> doneUpTo;
	set<int> newHeights;
	reverse(listOfHeights.begin(), listOfHeights.end());

	newHeights.insert(0);
	newHeights.insert(listOfHeights.back().second);

	doneUpTo.resize(listOfHeights.back().first+1);
	doneUpTo[0] = 1;
	doneUpTo[listOfHeights.back().second] = -1;
	listOfHeights.pop_back();
	reverse(listOfHeights.begin(), listOfHeights.end());

		// for(auto x: doneUpTo)
			// cerr << x << " ";
		// cerr << endl;

	long long ans = 0;
	for(auto &x: listOfHeights) {
		int H = x.first;
		int K = x.second;
		doneUpTo.resize(H+1);

		auto it = newHeights.lower_bound(H-K);
		bool oki = 0;
		int i;
		if(it != newHeights.end()) {
			oki = 1;
			i = *it;
		}

		auto bit = it;
		bool okj = 0;
		int j;
		if(bit != newHeights.begin()) {
			bit--;
			okj=1;
			j = *bit;
		}

		// for(auto x: newHeights)
			// cerr << x << " ";
		// cerr << endl;

		if(oki) {
			int toAdd = H-i;
			// cerr << i << " " << i+toAdd << endl;
			toAdd=min(toAdd,K);
			K -= toAdd;
			
			doneUpTo[i]++;
			if(doneUpTo[i]==0)
				newHeights.erase(i);

			doneUpTo[i+toAdd]--;
			if(doneUpTo[i+toAdd]==-1)
				newHeights.insert(i+toAdd);
		}

		if(okj) {
			// cerr << j << " " << j+K << endl;
			doneUpTo[j]++;
			if(doneUpTo[j]==0)
				newHeights.erase(j);

			doneUpTo[j+K]--;
			if(doneUpTo[j+K]==-1)
				newHeights.insert(j+K);
		}

		// for(auto x: doneUpTo)
			// cerr << x << " ";
		// cerr << endl;
	}

	for(int i = 0; i < doneUpTo.size()-1; i++) {
		if(i) doneUpTo[i] += doneUpTo[i-1];
		ans += (doneUpTo[i]*(doneUpTo[i]-1))/2;
		// cerr << doneUpTo[i] << " ";
	}
	// cerr << endl;
	cout << ans << endl;
}

Compilation message

sails.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
sails.cpp: In function 'int main()':
sails.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < doneUpTo.size()-1; i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
sails.cpp:27:6: warning: unused variable 'total' [-Wunused-variable]
  int total = 0;
      ^~~~~
sails.cpp:28:6: warning: unused variable 'mx' [-Wunused-variable]
  int mx = 0;
      ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 13 ms 1024 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2420 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2012 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3048 KB Output is correct
2 Correct 43 ms 3052 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5124 KB Output is correct
2 Correct 38 ms 3944 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3960 KB Output is correct
2 Correct 43 ms 2552 KB Output is correct