Submission #563983

#	Time	Username	Problem	Language	Result	Execution time	Memory
563983		tqbfjotld	Two Dishes (JOI19_dishes)	C++14	0 / 100	263 ms	37912 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
#define int long long

///segtree store amt can move right before die
///query rightmost num below bval
///shift B there (range dec everything to the right)
///if B gains a point then win, else try displace 1 as well

const int INF = 999999999999999999LL;

///range min
struct node{
    int s,e,v;
    int lazy;
    node *l,*r;
    node (int _s, int _e){
        s = _s; e = _e;
        if (s==e){
            v = INF;
        }
        else{
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
            v = min(l->v,r->v);
        }
    }
    void proc(){
        if (lazy==0) return;
        v += lazy;
        if (s!=e){
            l->lazy += lazy;
            r->lazy += lazy;
        }
        lazy = 0;
    }
    int descR(int val){
        proc();
        if (v>=val) return -1;
        if (s==e) return s;
        if (r->v<val) return r->descR(val);
        return l->descR(val);
    }
    void upd(int a, int b, int val){
        if (b<a) return;
        proc();
        if (a<=s && e<=b){
            lazy += val;
            proc();
            return;
        }
        if (b<=(s+e)/2){
            l->upd(a,b,val);
        }
        else if (a>(s+e)/2){
            r->upd(a,b,val);
        }
        else {
            l->upd(a,b,val);
            r->upd(a,b,val);
        }
        l->proc();r->proc();
        v = min(l->v,r->v);
    }
}*root;


int n,m;
int A[1000005];
int S[1000005];
int P[1000005];
int B[1000005];
int T[1000005];
int Q[1000005];

int prefA[1000005];
int prefB[1000005];

 main(){
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<n; x++){
        scanf("%lld%lld%lld",&A[x],&S[x],&P[x]);
    }
    for (int x = 0; x<m; x++){
        scanf("%lld%lld%lld",&B[x],&T[x],&Q[x]);
    }
    root = new node(0,n-1);
    for (int x = 1; x<=n; x++){
        prefA[x] = prefA[x-1]+A[x-1];
    }
    for (int x = 1; x<=m; x++){
        prefB[x] = prefB[x-1]+B[x-1];
    }
    int ans = 0;
    for (int x = 0; x<n; x++){
        if (prefA[x+1]<=S[x]){
            ans++;
            root->upd(x,x,-INF+S[x]-prefA[x+1]);
        }
    }
    int Bans = 0;
    int minv = -1;
    for (int x = 0; x<m; x++){
        int t = B[x];
        int t2 = root->descR(t);
        if (prefA[t2+1]+prefB[x+1]<=T[x]){
            t2 = max(t2,minv);
            Bans++;
            minv = t2;
            root->upd(t2+1,n-1,-B[x]);
        }
        else{
            root->upd(t2,t2,INF);
            int t3 = root->descR(t);
            root->upd(t2,t2,-INF);
            if (prefA[t3+1]+prefB[x+1]<=T[x] && minv<t2){
                t3 = max(t3,minv);
                minv = t3;
                root->upd(t3+1,n-1,-B[x]);
                root->upd(t2,t2,INF);
            }
            else{
                t2 = max(t2,minv);
                minv = t2;
                root->upd(t2+1,n-1,-B[x]);
            }
        }
    }
    printf("%lld",ans+Bans);
}

Compilation message (stderr)

dishes.cpp:79:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 |  main(){
      |  ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
dishes.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%lld%lld%lld",&A[x],&S[x],&P[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%lld%lld%lld",&B[x],&T[x],&Q[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9