oj.uz

Submission #563266

# Submission time Handle Problem Language Result Execution time Memory
563266 2022-05-16T16:52:18 Z karon Sails (IOI07_sails) C++14
40 / 100
 1000 ms 7220 KB 
#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

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){
      |               ^

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 280 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 17 ms 356 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 600 KB Output is correct
2 Correct 438 ms 6764 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 1352 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 1089 ms 1168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 1668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 7220 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 1082 ms 2144 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 1092 ms 2648 KB Time limit exceeded
2 Halted 0 ms 0 KB -