Submission #563266

#TimeUsernameProblemLanguageResultExecution timeMemory
563266karonSails (IOI07_sails)C++14
40 / 100
1092 ms7220 KiB
#include <bits/stdc++.h>
#define pb push_back
#define rs resize
#define debug printf("Hello\n")
#define Pi 3.141592653589793 
#define sz(a)                 ll((a).size()) 
#define all(x)                (x).begin(), (x).end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define mp make_pair
#define f first
#define s second
#define vt vector
#define rst(a,b) memset((a),(b), sizeof(a))
#define FOR(a, b, c) for (ll a = (b); (a) <  (c); ++(a))
#define FORE(a, b, c) for (ll a = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (ll a = (b); (a) >= (c); --(a))
#define umap unordered_map
#define len(a) (a).length()
#define pqueue priority_queue
 
using namespace std;
using vi = vector<int>;    
using ui = unsigned int;                
using ll = long long;                    
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;          
using pii = pair<int, int>;

const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
const char dir[4] = {'R', 'L', 'U', 'D'};
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;




void solve(){
	ll n;cin >> n;
	vt<pll> arr(n);
	FOR(i,0,n){
		ll a,b;cin >> a >> b;
		arr[i] = mp(a,b);
	}
	sort(all(arr));
	multiset<pll> q;
	ll t = arr[0].s;
	FOR(i,0,arr[0].f){
		if(t-->0)q.insert(mp(1,i));
		else q.insert(mp(0,i));
	}
	FOR(i,1,n){
		ll tmp = arr[i].s;
		queue<pll> toadd;
		if(q.size() < arr[i].f){
			FOR(j,q.size(),arr[i].f){
				q.insert(mp(0,j));
			}
		}
		while(tmp--){
			pll ff = *q.begin();
			q.erase(q.begin());
			toadd.push(mp(ff.f+1, ff.s));
		}
		while(toadd.size()){
			q.insert(toadd.front());
			toadd.pop();
		}
	}
	ll sum = 0;
	for(auto x : q){
		ll ff = x.f;
		sum += (ff)*(ff-1)/2;
	}
	
	cout << sum << endl;

}


int main(){
	fastio;
	solve();

}

Compilation message (stderr)

sails.cpp: In function 'void solve()':
sails.cpp:58:15: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |   if(q.size() < arr[i].f){
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...