oj.uz

Submission #1038821

# Submission time Handle Problem Language Result Execution time Memory
1038821 2024-07-30T08:00:28 Z ibm2006 Two Dishes (JOI19_dishes) C++17
49 / 100
 1066 ms 71508 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e18;
int n,m,i,j,k,l,r,x,y,z,w,t,range[1100000];
ll sum1[1100000],sum2[1100000],dp[1100000],add_cost[1100000],cost[1100000],c[1100000],d[1100000],seg[2200000],lazy[2200000],a[1100000],b[1100000],s;
vector<int> del_list[1100000],v;
set<pair<int,int>> chain;
pair<ll,ll> p,q;
pair<int,int> find_chain(int x)
{
    pair<int,int> p=*(--chain.lower_bound(make_pair(x,m+10)));
    return p;
}
void propagate(int x,int y,int z)
{
    if(z<1048576)
    {
        lazy[z*2]+=lazy[z];
        lazy[z*2+1]+=lazy[z];
    }
    seg[z]+=lazy[z];
    lazy[z]=0;
}
void f(int x,int y,int z,ll w)
{
    propagate(x,y,z);
    if(y<l||x>r)
        return;
    if(l<=x&&y<=r)
    {
        lazy[z]+=w;
        propagate(x,y,z);
        return;
    }
    f(x,(x+y)/2,z*2,w);
    f((x+y)/2+1,y,z*2+1,w);
    seg[z]=max(seg[z*2],seg[z*2+1]);
}
ll g(int x,int y,int z)
{
    propagate(x,y,z);
    if(y<l||x>r)
    {
        return -inf;
    }
    if(l<=x&&y<=r)
    {
        return seg[z];
    }
    return max(g(x,(x+y)/2,z*2),g((x+y)/2+1,y,z*2+1));
}
void add(int x,int y,ll z)
{
    l=x+1;
    r=y+1;
    f(1,1048576,1,z);
}
ll get_val(int x)
{
    l=x+1;
    r=x+1;
    return g(1,1048576,1);
}
void reconstruct_chain(int x)
{
    pair<int,int> p=find_chain(x);
    while(chain.upper_bound(p)!=chain.end())
    {
        pair<int,int> q=(*chain.upper_bound(p));
        y=get_val(p.second);
        z=get_val(q.first);
        //printf("(%lld,%lld,%lld,%lld)\n",p.first,p.second,q.first,q.second);
        if(z<=y+cost[p.second])
        {
            add(q.first,q.second,y+cost[p.second]-z);
            chain.erase(p);
            chain.erase(q);
            chain.insert({p.first,q.second});
            p.second=q.second;
        }
        else
            return;
    }
}
void show()
{
    return;
    ll i;
    for(i=0;i<=m;i++)
        printf("%lld ",get_val(i));
    printf("\n");
}
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%lld %lld %lld",&a[i],&c[i],&add_cost[i]);
        sum1[i]=sum1[i-1]+a[i];
    }
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&b[i],&d[i],&cost[i-1]);
        sum2[i]=sum2[i-1]+b[i];
    }
    for(i=1;i<=n;i++)
    {
        range[i]=upper_bound(sum2,sum2+m+1,c[i]-sum1[i])-sum2-1;
        //printf("(%lld) ",range[i]);
    }
    //printf("\n");
    for(i=1;i<=m;i++)
    {
        x=upper_bound(sum1,sum1+n+1,d[i]-sum2[i])-sum1;
        del_list[x].push_back(i-1);
        //printf("(%lld)",x);
    }
    //printf("\n");
    for(auto xx:del_list[0])
    {
        cost[xx]=0;
    }
    for(i=1;i<=m;i++)
    {
        dp[i]=dp[i-1]+cost[i-1];
    }
    for(i=0;i<=m;i++)
    {
        add(i,i,dp[i]);
    }
    /*for(i=0;i<=m;i++)
    {
        printf("(%lld)",cost[i]);
    }
    printf("\n");
    */chain.insert({0,m});
    for(i=1;i<=n;i++)
    {show();
    v.clear();
        for(auto xx:del_list[i])
        {
            p=find_chain(xx);
            chain.erase(p);
            chain.insert({p.first,xx});
            if(xx+1<=p.second)
            chain.insert({xx+1,p.second});
            cost[xx]=0;
            v.push_back(xx);
        }
        x=range[i];
        p=find_chain(x);
        if(x>=0)
        {
            chain.erase(p);
            chain.insert({p.first,x});
            if(x+1<=p.second)
            chain.insert({x+1,p.second});
            add(0,x,add_cost[i]);
        v.push_back(x);
        }
        sort(v.begin(),v.end());
        for(j=0;j<v.size();j++)
            reconstruct_chain(v[j]);
    }
    s=-inf;
    show();
    for(i=m;i<=m;i++)
    {
        s=max(s,get_val(i));
    }
    printf("%lld",s);
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for(j=0;j<v.size();j++)
      |                 ~^~~~~~~~~
dishes.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%lld %lld %lld",&a[i],&c[i],&add_cost[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%lld %lld %lld",&b[i],&d[i],&cost[i-1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 491 ms 62036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26456 KB Output is correct
2 Correct 10 ms 26460 KB Output is correct
3 Correct 10 ms 26460 KB Output is correct
4 Correct 10 ms 26340 KB Output is correct
5 Correct 10 ms 26460 KB Output is correct
6 Correct 10 ms 26460 KB Output is correct
7 Correct 10 ms 26388 KB Output is correct
8 Correct 14 ms 26460 KB Output is correct
9 Correct 11 ms 26460 KB Output is correct
10 Correct 11 ms 26344 KB Output is correct
11 Correct 10 ms 26284 KB Output is correct
12 Correct 10 ms 26460 KB Output is correct
13 Correct 11 ms 26456 KB Output is correct
14 Correct 10 ms 26460 KB Output is correct
15 Correct 10 ms 26244 KB Output is correct
16 Correct 10 ms 26460 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26456 KB Output is correct
2 Correct 10 ms 26460 KB Output is correct
3 Correct 10 ms 26460 KB Output is correct
4 Correct 10 ms 26340 KB Output is correct
5 Correct 10 ms 26460 KB Output is correct
6 Correct 10 ms 26460 KB Output is correct
7 Correct 10 ms 26388 KB Output is correct
8 Correct 14 ms 26460 KB Output is correct
9 Correct 11 ms 26460 KB Output is correct
10 Correct 11 ms 26344 KB Output is correct
11 Correct 10 ms 26284 KB Output is correct
12 Correct 10 ms 26460 KB Output is correct
13 Correct 11 ms 26456 KB Output is correct
14 Correct 10 ms 26460 KB Output is correct
15 Correct 10 ms 26244 KB Output is correct
16 Correct 10 ms 26460 KB Output is correct
17 Correct 13 ms 26716 KB Output is correct
18 Correct 14 ms 26716 KB Output is correct
19 Correct 18 ms 26712 KB Output is correct
20 Correct 15 ms 26716 KB Output is correct
21 Correct 20 ms 26936 KB Output is correct
22 Correct 18 ms 26716 KB Output is correct
23 Correct 18 ms 26716 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26456 KB Output is correct
2 Correct 10 ms 26460 KB Output is correct
3 Correct 10 ms 26460 KB Output is correct
4 Correct 10 ms 26340 KB Output is correct
5 Correct 10 ms 26460 KB Output is correct
6 Correct 10 ms 26460 KB Output is correct
7 Correct 10 ms 26388 KB Output is correct
8 Correct 14 ms 26460 KB Output is correct
9 Correct 11 ms 26460 KB Output is correct
10 Correct 11 ms 26344 KB Output is correct
11 Correct 10 ms 26284 KB Output is correct
12 Correct 10 ms 26460 KB Output is correct
13 Correct 11 ms 26456 KB Output is correct
14 Correct 10 ms 26460 KB Output is correct
15 Correct 10 ms 26244 KB Output is correct
16 Correct 10 ms 26460 KB Output is correct
17 Correct 13 ms 26716 KB Output is correct
18 Correct 14 ms 26716 KB Output is correct
19 Correct 18 ms 26712 KB Output is correct
20 Correct 15 ms 26716 KB Output is correct
21 Correct 20 ms 26936 KB Output is correct
22 Correct 18 ms 26716 KB Output is correct
23 Correct 18 ms 26716 KB Output is correct
24 Correct 377 ms 56920 KB Output is correct
25 Correct 413 ms 67152 KB Output is correct
26 Correct 312 ms 56804 KB Output is correct
27 Correct 422 ms 71508 KB Output is correct
28 Correct 394 ms 57780 KB Output is correct
29 Correct 198 ms 57284 KB Output is correct
30 Correct 1066 ms 59992 KB Output is correct
31 Correct 199 ms 50596 KB Output is correct
32 Correct 165 ms 37716 KB Output is correct
33 Correct 593 ms 58308 KB Output is correct
34 Correct 696 ms 62032 KB Output is correct
35 Correct 1034 ms 55196 KB Output is correct
36 Correct 982 ms 55120 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26456 KB Output is correct
2 Correct 10 ms 26460 KB Output is correct
3 Correct 10 ms 26460 KB Output is correct
4 Correct 10 ms 26340 KB Output is correct
5 Correct 10 ms 26460 KB Output is correct
6 Correct 10 ms 26460 KB Output is correct
7 Correct 10 ms 26388 KB Output is correct
8 Correct 14 ms 26460 KB Output is correct
9 Correct 11 ms 26460 KB Output is correct
10 Correct 11 ms 26344 KB Output is correct
11 Correct 10 ms 26284 KB Output is correct
12 Correct 10 ms 26460 KB Output is correct
13 Correct 11 ms 26456 KB Output is correct
14 Correct 10 ms 26460 KB Output is correct
15 Correct 10 ms 26244 KB Output is correct
16 Correct 10 ms 26460 KB Output is correct
17 Correct 13 ms 26716 KB Output is correct
18 Correct 14 ms 26716 KB Output is correct
19 Correct 18 ms 26712 KB Output is correct
20 Correct 15 ms 26716 KB Output is correct
21 Correct 20 ms 26936 KB Output is correct
22 Correct 18 ms 26716 KB Output is correct
23 Correct 18 ms 26716 KB Output is correct
24 Correct 377 ms 56920 KB Output is correct
25 Correct 413 ms 67152 KB Output is correct
26 Correct 312 ms 56804 KB Output is correct
27 Correct 422 ms 71508 KB Output is correct
28 Correct 394 ms 57780 KB Output is correct
29 Correct 198 ms 57284 KB Output is correct
30 Correct 1066 ms 59992 KB Output is correct
31 Correct 199 ms 50596 KB Output is correct
32 Correct 165 ms 37716 KB Output is correct
33 Correct 593 ms 58308 KB Output is correct
34 Correct 696 ms 62032 KB Output is correct
35 Correct 1034 ms 55196 KB Output is correct
36 Correct 982 ms 55120 KB Output is correct
37 Incorrect 457 ms 59348 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26456 KB Output is correct
2 Correct 10 ms 26460 KB Output is correct
3 Correct 10 ms 26460 KB Output is correct
4 Correct 10 ms 26340 KB Output is correct
5 Correct 10 ms 26460 KB Output is correct
6 Correct 10 ms 26460 KB Output is correct
7 Correct 10 ms 26388 KB Output is correct
8 Correct 14 ms 26460 KB Output is correct
9 Correct 11 ms 26460 KB Output is correct
10 Correct 11 ms 26344 KB Output is correct
11 Correct 10 ms 26284 KB Output is correct
12 Correct 10 ms 26460 KB Output is correct
13 Correct 11 ms 26456 KB Output is correct
14 Correct 10 ms 26460 KB Output is correct
15 Correct 10 ms 26244 KB Output is correct
16 Correct 10 ms 26460 KB Output is correct
17 Correct 13 ms 26716 KB Output is correct
18 Correct 14 ms 26716 KB Output is correct
19 Correct 18 ms 26712 KB Output is correct
20 Correct 15 ms 26716 KB Output is correct
21 Correct 20 ms 26936 KB Output is correct
22 Correct 18 ms 26716 KB Output is correct
23 Correct 18 ms 26716 KB Output is correct
24 Correct 377 ms 56920 KB Output is correct
25 Correct 413 ms 67152 KB Output is correct
26 Correct 312 ms 56804 KB Output is correct
27 Correct 422 ms 71508 KB Output is correct
28 Correct 394 ms 57780 KB Output is correct
29 Correct 198 ms 57284 KB Output is correct
30 Correct 1066 ms 59992 KB Output is correct
31 Correct 199 ms 50596 KB Output is correct
32 Correct 165 ms 37716 KB Output is correct
33 Correct 593 ms 58308 KB Output is correct
34 Correct 696 ms 62032 KB Output is correct
35 Correct 1034 ms 55196 KB Output is correct
36 Correct 982 ms 55120 KB Output is correct
37 Incorrect 457 ms 59348 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 491 ms 62036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 491 ms 62036 KB Output isn't correct
2 Halted 0 ms 0 KB -