oj.uz

답안 #996796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
996796 2024-06-11T08:36:48 Z modwwe Team Contest (JOI22_team) C++17
9 / 100
 309 ms 17104 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 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 8796 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 2 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Incorrect 2 ms 8796 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 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 8796 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 2 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Incorrect 2 ms 8796 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 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 8796 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 2 ms 8800 KB Output is correct
11 Correct 253 ms 16844 KB Output is correct
12 Correct 179 ms 15312 KB Output is correct
13 Correct 257 ms 16064 KB Output is correct
14 Correct 260 ms 17016 KB Output is correct
15 Correct 279 ms 17100 KB Output is correct
16 Correct 309 ms 17104 KB Output is correct

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 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 8796 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 2 ms 8800 KB Output is correct
11 Correct 253 ms 16844 KB Output is correct
12 Correct 179 ms 15312 KB Output is correct
13 Correct 257 ms 16064 KB Output is correct
14 Correct 260 ms 17016 KB Output is correct
15 Correct 279 ms 17100 KB Output is correct
16 Correct 309 ms 17104 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8792 KB Output is correct
19 Correct 1 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 252 ms 17020 KB Output is correct
23 Incorrect 260 ms 16844 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 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 8796 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 2 ms 8800 KB Output is correct
11 Correct 253 ms 16844 KB Output is correct
12 Correct 179 ms 15312 KB Output is correct
13 Correct 257 ms 16064 KB Output is correct
14 Correct 260 ms 17016 KB Output is correct
15 Correct 279 ms 17100 KB Output is correct
16 Correct 309 ms 17104 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8792 KB Output is correct
19 Correct 1 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 252 ms 17020 KB Output is correct
23 Incorrect 260 ms 16844 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8796 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 8796 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 2 ms 8800 KB Output is correct
11 Correct 253 ms 16844 KB Output is correct
12 Correct 179 ms 15312 KB Output is correct
13 Correct 257 ms 16064 KB Output is correct
14 Correct 260 ms 17016 KB Output is correct
15 Correct 279 ms 17100 KB Output is correct
16 Correct 309 ms 17104 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 1 ms 8792 KB Output is correct
19 Correct 1 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 252 ms 17020 KB Output is correct
23 Incorrect 260 ms 16844 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 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 8796 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 2 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Incorrect 2 ms 8796 KB Output isn't correct
19 Halted 0 ms 0 KB -