Submission #1261710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261710		niepamietamhasla	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	2 ms	4928 KiB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll,ll>

const ll MAXN = 2e5 + 5;


ll n, m;

ll V[MAXN];
ll V2[MAXN];

struct d{
    ll a;
    ll b;
    ll c;
};

vector<d> ludzie[MAXN];

struct comp{
    bool operator()(const d &p1, const d &p2){
        if(p1.b != p2.b) return p1.b < p2.b;
        return false;
    }
};

bool czy(ll F, ll k, ll koniec){
    //cout << F << " " << k << " " << koniec << " BS\n";
    ll pom = 0;
    priority_queue<d, vector<d>, comp> pq;
    for(ll i = 1; i <= n; ++i){
        V2[i] = 0;
    }
    for(ll i = 1; i <= koniec; ++i){
        for(auto u : ludzie[i]){
            if(u.b >= koniec){
                pq.push(u);
            } 
        }
        ll ile = max(0ll, (V[i] - pom - k + F + 1) / 2);
        while(ile > 0){
            if(pq.empty()) return false;
            auto e = pq.top();
            pq.pop();
            ll plus;
            if(ile >= e.c){
                plus = e.c;
                ile -= e.c;
            }
            else{
                plus = ile;
                ile = 0;
                pq.push({e.a, e.b, e.c - plus});
            }
            F -= plus;
            pom += plus;
            V2[e.a] -= 2 * plus;
            V2[e.b+1] += 2 * plus;
            V2[0] += plus;
        }   
    }
    for(ll i = 1; i <= n; ++i){
        V2[i] += V2[i-1];
        if(V2[i] > k) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    ll a, b, c;
    for(ll i = 0; i < m; ++i){
        cin >> a >> b >> c; 
        if(a > b) swap(a, b);
        b--;
        ludzie[a].push_back((d){a, b, c});
        V[a] += c;
        V[b+1]-= c;
    }
    ll mx = 0;
    ll ind = -1;
    for(ll i = 1; i <= n; ++i){
        V[i] += V[i - 1];
//        cout << V[i] << " ";
        if(V[i] >= mx){
            mx = V[i];
            ind = i;
        }
    }
    ll p = 1;
    ll k = mx;
    while(p != k){
        ll sr = (p + k) / 2;
        if(czy(mx - sr, sr, ind) or czy(mx - sr + 1, sr, ind)){
            k = sr;
        }
        else{
            p = sr + 1;
        }
    }
    cout << p << "\n";

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15