Submission #9756358


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];} 
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";} cout<<endl;
#define S second
#define F first
#define SZ(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const int  MOD = 1e9 + 7;
const int  N = 1e6 + 7;
const int  M = 1e4 ;

void solve(){
    ll n , d , a;
    cin>>n>>d>>a;
    vector<pair < ll , ll > > v(n);
    for(int i = 0 ; i < n ; i++){
        cin>>v[i].F>>v[i].S;
    }
    sort(v.begin(), v.end());
    queue< pair< ll , ll > > q;
    ll sum = 0;
    ll res = 0;
    for(int i = 0 ; i < n; i++){
        while(q.size() > 0 && q.front().F < v[i].F){
            sum -= q.front().S;
            q.pop();
        }
        v[i].S -= a * sum;
        if(v[i].S <= 0) continue;

        ll tmp = (v[i].S + a - 1) / a;
        res += tmp;
        q.push({v[i].F + 2 * d, tmp});
        sum += tmp;
    }
    cout<<res<<endl;
}	
 
int main(){
    ios::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
    int t = 1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

Submission Info

Submission Time
Task F - Silver Fox vs Monster
User duridia
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1217 Byte
Status
Exec Time 60 ms
Memory 4992 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01, sample_02, sample_03
All 600 / 600 hand_01, hand_02, max_01, max_02, max_03, max_04, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, random_15, random_16, sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
hand_01 1 ms 256 KB
hand_02 1 ms 256 KB
max_01 59 ms 3456 KB
max_02 60 ms 3456 KB
max_03 46 ms 4992 KB
max_04 46 ms 4992 KB
random_01 18 ms 1280 KB
random_02 8 ms 640 KB
random_03 51 ms 3072 KB
random_04 33 ms 2176 KB
random_05 56 ms 3328 KB
random_06 30 ms 1920 KB
random_07 5 ms 512 KB
random_08 49 ms 3072 KB
random_09 8 ms 768 KB
random_10 32 ms 2048 KB
random_11 3 ms 384 KB
random_12 22 ms 1408 KB
random_13 35 ms 2304 KB
random_14 13 ms 1024 KB
random_15 50 ms 3200 KB
random_16 51 ms 3072 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB