Submission #117632

#	Time	Username	Problem	Language	Result	Execution time	Memory
117632		KieranHorgan	Sails (IOI07_sails)	C++17	100 / 100	66 ms	5124 KiB

sails

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

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 / 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