Submission #126503

#	Time	Username	Problem	Language	Result	Execution time	Memory
126503		ainta	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	2 ms	376 KiB

arranging_tickets

#include<cstdio>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, m;
struct point{
    int a, b, c;
    bool operator <(point &p)const {
        return a < p.a;
    }
}w[201000];
long long S[201000], Z[201000], H[201000];
struct Tree{
    long long Mn[SZ+SZ], K[SZ+SZ];
    void UDT(int nd){
        Mn[nd] = min(Mn[nd*2],Mn[nd*2+1]);
    }
    void init(int nd, int b, int e) {
        K[nd] = 0;
        if (b == e) {
            Mn[nd] = H[b];
            return;
        }
        int m = (b+e)>>1;
        init(nd*2,b,m);
        init(nd*2+1,m+1,e);
        UDT(nd);
    }
    void Add2(int nd, int x){
        Mn[nd] += x;
        K[nd] += x;
    }
    void Spread(int nd){
        Add2(nd*2,K[nd]);
        Add2(nd*2+1,K[nd]);
        K[nd] = 0;
    }
    void Add(int nd, int b, int e, int s, int l, int x){
        if(s<=b && e<=l){
            Add2(nd, x);
            return;
        }
        Spread(nd);
        int m = (b+e)>>1;
        if(s<=m)Add(nd*2,b,m,s,l,x);
        if(l>m)Add(nd*2+1,m+1,e,s,l,x);
        UDT(nd);
    }
    long long Min(int nd, int b, int e, int s, int l){
        if(s>l)return (long long)1e18;
        if(s<=b && e<=l)return Mn[nd];
        Spread(nd);
        int m = (b+e)>>1;
        long long r=1e18;
        if(s<=m)r = min(Min(nd*2,b,m,s,l),r);
        if(l>m)r = min(Min(nd*2+1,m+1,e,s,l),r);
        return r;
    }
}T;
int pv;
long long Get(){
    int i;
    T.init(1, 0, n-1);
    long long res=0;
    for(i=1;i<=m;i++){
        long long t = min(min(T.Min(1, 0, n-1, 0, w[i].a-1), T.Min(1, 0, n-1, w[i].b, n-1)),(long long)w[i].c);
        res+=t;
        T.Add(1,0,n-1,0,w[i].a-1,-t);
        T.Add(1,0,n-1,w[i].b,n-1,-t);
    }
    return res;
}
bool Pos(long long M){
    int i, j;
    long long bb = Z[pv] - M, ee = M/2;
    for(i=bb;i<=bb+1;i++){
        for(j=0;j<n;j++){
            H[j] = (i+M-Z[j])/2;
        }
        if(H[0] < i)continue;
        if(Get()>=i)return true;
    }
    return false;
}
int main(){
    int i;
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a>b)swap(a,b);
        w[i] = {a,b,c};;
        S[a]+=c;
        S[b]-=c;
    }
    sort(w+1,w+m+1);
    long long Mx = -1;
    pv = -1;
    for(i=1;i<n;i++){
        S[i]+=S[i-1];
        if(Mx < S[i]){
            Mx = S[i];
            pv = i;
        }
    }
    for(i=1;i<=pv;i++)Z[i]=max(Z[i-1],S[i]);
    for(i=n-1;i>=pv;i--)Z[i] = max(Z[i+1],S[i]);
    long long b = 0, e = Mx - 1, mid, r = Mx;
    while(b<=e){
        mid = (b+e)>>1;
        if(Pos(mid)){
            r = mid;
            e = mid - 1;
        }
        else b = mid + 1;
    }
    printf("%lld\n",r);
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
arranging_tickets.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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