oj.uz

Submission #1010885

# Submission time Handle Problem Language Result Execution time Memory
1010885 2024-06-29T13:13:22 Z modwwe Two Dishes (JOI19_dishes) C++17
0 / 100
 133 ms 38892 KB 
//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s0,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l,l2,r2,l3,l4;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
///     fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
ic a[1000007];
ic b[1000007];
ic c[1000007];
ic d[1000007];
struct fen_wick
{
    int bit[1000007];
    void upd(int x,int y)
    {
        for(x; x; x-=x&-x) bit[x]+=y;
    }
    int get(int x)
    {
        int s=0;
        for(x; x<=max(n,m); x+=x&-x)s+=bit[x];
        return s;
    }
} fen[4];
bool cmp(ic a,ic b)
{
    return a.a<b.a;
}

void phongbeo()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i].a>>a[i].b>>a[i].c,
            a[i].a+=a[i-1].a,
                    c[i]= {a[i].b-a[i].a,a[i].c,i},
                          fen[0].upd(i,a[i].c),
                          fen[2].upd(i,a[i].c);

    for(int i=1; i<=m; i++)
        cin>>b[i].a>>b[i].b>>b[i].c,
            b[i].a+=b[i-1].a,
                    d[i]= {b[i].b-b[i].a,b[i].c,i},
                          fen[1].upd(i,b[i].c),
                          fen[3].upd(i,b[i].c);
    sort(c+1,c+1+n,cmp);
    sort(d+1,d+1+m,cmp);
    l=1;
    l2=1;
    r=0;
    r2=0;
    l3=1;
    l4=1;
    while(c[l3].a<b[0].a&&l3<=n)
    {
        fen[0].upd(c[l3].c,-c[l3].b);
        l3++;
    }
    while(d[l4].a<a[0].a&&l4<=m)
    {
        fen[1].upd(d[l4].c,-d[l4].b);
        l4++;
    }
    while(c[l].a<b[1].a&&l<=n)
    {
        fen[2].upd(c[l].c,-c[l].b);
        l++;
    }
    while(d[l2].a<a[1].a&&l2<=m)
    {
        fen[3].upd(d[l2].c,-d[l2].b);

        l2++;
    }
    s2=fen[2].get(1);
    s0=fen[0].get(1);
    s1=fen[1].get(1);
    s3=fen[3].get(1);
    for(int i=1; i<=n+m; i++)
    {
        if(s0-s2<=s1-s3)
        {
            r2++;
            while(c[l].a<b[r2+1].a&&l<=n)
            {
                fen[2].upd(c[l].c,-c[l].b);
                l++;
            }
            while(c[l3].a<b[r2].a&&l3<=n)
      {
          fen[0].upd(c[l3].c,-c[l3].b);
          l3++;
      }

            s2=fen[2].get(r+1);
            s0=fen[0].get(r+1);
           s1=fen[1].get(r2+1);
            s3=fen[3].get(r2+1);
            if(r==n)
            {
                s1=inf;
                s3=-inf;
            }
            if(r2==m)
            {
                s0=inf;
                s2=-inf;
            }
            if(b[r2].a+a[r].a<=b[r2].b)s7+=b[r2].c;
        }
        else
        {
            r++;
            while(d[l2].a<a[r+1].a&&l2<=m)
            {
                fen[3].upd(d[l2].c,-d[l2].b);
                l2++;
            }
             while(d[l4].a<a[r].a&&l4<=m)
    {
        fen[1].upd(d[l4].c,-d[l4].b);
        l4++;
    }
            s2=fen[2].get(r+1);
            s0=fen[0].get(r+1);
            s1=fen[1].get(r2+1);
            s3=fen[3].get(r2+1);
            if(r2==m)
            {
                s0=inf;
                s2=-inf;
            }
            if(r==n)
            {
                s1=inf;
                s3=-inf;
            }
            if(b[r2].a+a[r].a<=a[r].b)s7+=a[r].c;
        }
    }
    cout<<s7;
}

Compilation message

dishes.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main()
      | ^~~~
dishes.cpp: In member function 'void fen_wick::upd(long long int, long long int)':
dishes.cpp:67:13: warning: statement has no effect [-Wunused-value]
   67 |         for(x; x; x-=x&-x) bit[x]+=y;
      |             ^
dishes.cpp: In member function 'long long int fen_wick::get(long long int)':
dishes.cpp:72:13: warning: statement has no effect [-Wunused-value]
   72 |         for(x; x<=max(n,m); x+=x&-x)s+=bit[x];
      |             ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 38892 KB Output is correct
2 Incorrect 129 ms 38812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 38892 KB Output is correct
2 Incorrect 129 ms 38812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 38892 KB Output is correct
2 Incorrect 129 ms 38812 KB Output isn't correct
3 Halted 0 ms 0 KB -