Submission #815112

#	Time	Username	Problem	Language	Result	Execution time	Memory
815112		79brue	Arranging Tickets (JOI17_arranging_tickets)	C++17	100 / 100	1172 ms	18460 KiB

arranging_tickets

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int ex[200002], ey[200002]; ll ew[200002];
ll arr[200002], tarr[200002];
ll lim[200002];
ll flipCnt[200002];

vector<int> toSee[200002];

struct dat{
    int r, idx; ll cnt;
    dat(){}
    dat(int r, int idx, ll cnt): r(r), idx(idx), cnt(cnt){}
    bool operator<(const dat &nxt)const{
        return r<nxt.r;
    }
};

bool able(int x, ll MX, ll flip){
    if(flip < 0) return false;
    lim[0] = MX + flip;
    for(int i=1; i<n; i++) lim[i] = MX + flip - arr[i];
    for(int i=2; i<x; i++) lim[i] = min(lim[i], lim[i-1]);
    for(int i=n-2; i>x; i--) lim[i] = min(lim[i], lim[i+1]);
    for(int i=0; i<n; i++) lim[i] /= 2;
    for(int i=0; i<n; i++) lim[i] = min(lim[i], flip);
    for(int i=1; i<=k; i++) flipCnt[i] = 0;

    priority_queue<dat> pq;
    for(int s=1; s<=x; s++){
        for(int idx: toSee[s]) if(ey[idx] >= x+1) pq.push(dat(ey[idx], idx, ew[idx]));
        if(lim[s-1] == lim[s] && s != x) continue;
        ll val = lim[s-1] - (s==x ? 0 : lim[s]);
        while(val > 0){
            if(pq.empty()) break;
            dat tmp = pq.top(); pq.pop();
            ll take = min(val, tmp.cnt);
            flipCnt[tmp.idx] += take, tmp.cnt -= take, val -= take, flip -= take;
            if(tmp.cnt) pq.push(tmp);
        }
    }
    if(flip > 0) return false;

    for(int i=1; i<=n; i++) tarr[i] = 0;
    for(int i=1; i<=k; i++){
        tarr[ex[i]] += ew[i] - flipCnt[i], tarr[ey[i]] -= ew[i] - flipCnt[i];
        tarr[1] += flipCnt[i], tarr[ex[i]] -= flipCnt[i];
        tarr[ey[i]] += flipCnt[i], tarr[n+1] -= flipCnt[i];
    }
    for(int i=1; i<=n; i++){
        tarr[i] += tarr[i-1];
        if(tarr[i] > MX) return false;
    }
    return true;
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=k; i++){
        scanf("%d %d %lld", &ex[i], &ey[i], &ew[i]);
        if(ex[i] > ey[i]) swap(ex[i], ey[i]);
        toSee[ex[i]].push_back(i);
    }

    /// 1. 초기 구간별 합을 구해 준다
    for(int i=1; i<=k; i++) arr[ex[i]] += ew[i], arr[ey[i]] -= ew[i];
    for(int i=1; i<=n; i++) arr[i] += arr[i-1];

    int x = max_element(arr+1, arr+n) - arr; /// 최댓값 위치

    /// 2. 답에 대한 이분 탐색
    ll L = 0, R = arr[x], ANS = R;
    while(L <= R){
        ll M = (L+R)/2;
        if(able(x, M, arr[x] - M) || able(x, M, arr[x] - M + 1)) ANS = M, R = M-1;
        else L = M+1;
    }

    printf("%lld", ANS);
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
arranging_tickets.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d %d %lld", &ex[i], &ey[i], &ew[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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