oj.uz

Submission #996794

# Submission time Handle Problem Language Result Execution time Memory
996794 2024-06-11T08:35:04 Z modwwe Team Contest (JOI22_team) C++17
9 / 100
 315 ms 19348 KB 
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#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".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
const int inf=1e9;
void phongbeo();
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,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
    //fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
    checktime
}
int bit[450001];
void reset()
{
    for(int i=1; i<=n*3; i++) bit[i]=3*n+1;
}
void upd(int x,int y)
{
    for(x; x; x-=x&-x) bit[x]=min(bit[x],y);
}
int get(int x)
{
    int ss=3*n+1;
    for(x; x<=n*3; x+=x&-x)ss=min(ss,bit[x]);
    return ss;
}
bool cmp(id a,id b)
{
    if(a.a==b.a)return a.c>b.c;
    return a.a<b.a;
}
int d[150001];
id a[150001];
vector<int> v;
vector<int> v2;
vector<int> v3;
bool cmp2(id a,id b)
{
    if(a.c==b.c)return a.a<b.a;
    return a.c>b.c;
}
void solve()
{
    /// muc dich ham solve :
    /// sort theo ac
    /// aa dung cuoi
    /// ab dung giua
    /// ta co goi b1 b2 b3 la thu tu
    /// b1.a<b2.a<b3.a
///b1.c>b2.c>b3.c
///b1.b<b2.b>b3.b
    sort(a+1,a+1+n,cmp);
    reset();
    for(int i=1; i<=n; i++)
    {
        l=a[i].c+1;
        r=n*3;
        s2=-1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(get(mid)<a[i].b)l=mid+1,s2=mid;
            else r=mid-1;
        }
        if(s2!=-1)d[a[i].d]=v[s2-1]+v[a[i].b-1];
        else  d[a[i].d]=-1e9,upd(a[i].c,a[i].b);
    }
    sort(a+1,a+1+n,cmp2);
    reset();
    for(int i=n; i>=1; --i)
    {
        l=a[i].a+1;
        r=n*3;
        s2=-1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(get(mid)<a[i].b)
                l=mid+1,s2=mid;
            else r=mid-1;
        }
        if(s2!=-1)
        {
            s3=max(s3,d[a[i].d]+v[s2-1]);
        }
        else upd(a[i].a,a[i].b);
    }
/// cot chon thu 2 se la cot 2 va co cot 1 lon thu h2

}
vector<int> v4[150001];
void phongbeo()
{
    cin>>n;
    reset();
    for(int i=1; i<=n; i++)
        cin>>a[i].a>>a[i].b>>a[i].c,a[i].d=i,
                                        v.pb(a[i].a),
                                        v.pb(a[i].b);
    v.pb(a[i].c);
    sort(v.begin(),v.end());
    for(int i=1; i<=n; i++)
        a[i].a=lower_bound(v.begin(),v.end(),a[i].a)-v.begin()+1,
            a[i].b=lower_bound(v.begin(),v.end(),a[i].b)-v.begin()+1,
                a[i].c=lower_bound(v.begin(),v.end(),a[i].c)-v.begin()+1;
    s3=-1;
    solve();
    for(int i=1; i<=n; i++)
        swap(a[i].a,a[i].b);
    solve();
    for(int i=1; i<=n; i++)
        swap(a[i].a,a[i].b);
    for(int i=1; i<=n; i++)
        swap(a[i].c,a[i].b);
    solve();
    cout<<s3;
}

Compilation message

team.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main()
      | ^~~~
team.cpp: In function 'void upd(long long int, long long int)':
team.cpp:62:9: warning: statement has no effect [-Wunused-value]
   62 |     for(x; x; x-=x&-x) bit[x]=min(bit[x],y);
      |         ^
team.cpp: In function 'long long int get(long long int)':
team.cpp:67:9: warning: statement has no effect [-Wunused-value]
   67 |     for(x; x<=n*3; x+=x&-x)ss=min(ss,bit[x]);
      |         ^
team.cpp: In function 'void solve()':
team.cpp:104:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |             int mid=l+r>>1;
      |                     ~^~
team.cpp:120:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |             int mid=l+r>>1;
      |                     ~^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8828 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8832 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8792 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Incorrect 2 ms 8864 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8828 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8832 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8792 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Incorrect 2 ms 8864 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8840 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8804 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 1 ms 8624 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 275 ms 18528 KB Output is correct
12 Correct 185 ms 15056 KB Output is correct
13 Correct 274 ms 15736 KB Output is correct
14 Correct 314 ms 18896 KB Output is correct
15 Correct 287 ms 18384 KB Output is correct
16 Correct 315 ms 18388 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8840 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8804 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 1 ms 8624 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 275 ms 18528 KB Output is correct
12 Correct 185 ms 15056 KB Output is correct
13 Correct 274 ms 15736 KB Output is correct
14 Correct 314 ms 18896 KB Output is correct
15 Correct 287 ms 18384 KB Output is correct
16 Correct 315 ms 18388 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 4 ms 8796 KB Output is correct
22 Correct 290 ms 19348 KB Output is correct
23 Incorrect 302 ms 18628 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8840 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8804 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 1 ms 8624 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 275 ms 18528 KB Output is correct
12 Correct 185 ms 15056 KB Output is correct
13 Correct 274 ms 15736 KB Output is correct
14 Correct 314 ms 18896 KB Output is correct
15 Correct 287 ms 18384 KB Output is correct
16 Correct 315 ms 18388 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 4 ms 8796 KB Output is correct
22 Correct 290 ms 19348 KB Output is correct
23 Incorrect 302 ms 18628 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8840 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8804 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 1 ms 8624 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 275 ms 18528 KB Output is correct
12 Correct 185 ms 15056 KB Output is correct
13 Correct 274 ms 15736 KB Output is correct
14 Correct 314 ms 18896 KB Output is correct
15 Correct 287 ms 18384 KB Output is correct
16 Correct 315 ms 18388 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8796 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 4 ms 8796 KB Output is correct
22 Correct 290 ms 19348 KB Output is correct
23 Incorrect 302 ms 18628 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8828 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8832 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8792 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Incorrect 2 ms 8864 KB Output isn't correct
15 Halted 0 ms 0 KB -