oj.uz

답안 #991063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991063 2024-06-01T08:02:46 Z User0069 팀들 (IOI15_teams) C++17
77 / 100
 4000 ms 379184 KB 
#include<bits/stdc++.h>
#include"teams.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=5e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
int N;
struct node
{
    node *l,*r;
    int val;
    node():l(NULL),r(NULL),val(0){};
};
node* root[maxn];
vector<int> v[maxn];
node* cons(node* kk,int cl,int cr)
{
    kk=new node();
    if(cl==cr)
    {
        return kk;
    }
    int mid=(cl+cr)/2;
    kk->l=cons(kk->l,cl,mid);
    kk->r=cons(kk->r,mid+1,cr);
    return kk;
}
node* update(node* kk,int cl,int cr,int pos,int val)
{
    node* kkk=new node();
    kkk->l=kk->l;
    kkk->r=kk->r;
    kkk->val=kk->val;
    if(cl==cr)
    {
        kkk->val+=val;
        return kkk;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) kkk->l=update(kk->l,cl,mid,pos,val);
    else kkk->r=update(kk->r,mid+1,cr,pos,val);
    kkk->val=kkk->l->val+kkk->r->val;
    return kkk;
}
int get(node* kk,int cl,int cr,int l,int r )
{
    if(cl>r||cr<l) return 0;
    if(cl>=l&&cr<=r) return kk->val;
    int mid=(cl+cr)/2;
    return get(kk->l,cl,mid,l,r)+get(kk->r,mid+1,cr,l,r);
}
int cnt(int a,int b,int c,int d)
{
    return get(root[b],0,N,c,d)-((a>0)?get(root[a-1],0,N,c,d):0);
}
void init(int32_t n,int32_t* a,int32_t* b)
{
    N=n;
    root[0]=cons(root[0],0,n);
    for(int i=0;i<n;i++)
    {
        v[b[i]].push_back(a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        for(int x:v[i])
        {
            root[i]=update(root[i],0,n,x,1);
        }
    }
    root[n+1]=root[n];
}
struct ele
{
    int a,b,range,rmd;
};
int32_t can(int32_t m,int32_t* k)
{
    sort(k,k+m);
//    vector<pii> v;
//    int cur=k[0],num=1;
//    for(int i=1;i<m;i++)
//    {
//        if(k[i]==cur)
//        {
//            num++;
//        }
//        else
//        {
//            v.push_back({cur,num});
//            num=1;
//            cur=k[i];
//        }
//    }
//    v.push_back({cur,num});
    vector<ele> st;
    st.push_back({0,0,N,0});
    for(int i=0;i<m;i++)
    {
        int prev,late,a,b,sum=0;
        a=k[i];
        prev=st.back().a;
        b=prev+1;
        late=(i==m-1)?N+1:k[i+1];
        int ra=k[i]-1;
        int lmao=-1;
        while(st.back().range<=ra)
        {
            lmao=st.back().b;
            st.pop_back();
        }
        if(lmao!=-1) st.push_back({prev,lmao,ra,0});
//        for(ele w:st)
//        {
//            cout<<w.a<<" "<<w.b<<" "<<w.range<<" "<<w.rmd<<" ; ";
//        }
//        cout<<"\n";
        while(!st.empty()&&sum+(lmao=cnt(ra+1,st.back().range,b,k[i]))<k[i])
        {
            b=st.back().b;
            sum+=lmao+st.back().rmd;
            ra=st.back().range;
            st.pop_back();
        }
        if(st.empty()) return 0;
        int l=ra,r=st.back().range,ans=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(sum+cnt(ra+1,mid,b,k[i])>=k[i])
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        st.push_back({a,b,ans,sum+cnt(ra+1,ans,b,k[i])-k[i]});
//        for(ele w:st)
//        {
//            cout<<w.a<<" "<<w.b<<" "<<w.range<<" "<<w.rmd<<" ; ";
//        }
//        cout<<"\n";
    }
    return 1;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname"1.OUT","w",stdout);
//    }
//    Faster
//    int n,q;
//    cin>>n>>q;
//    int32_t _a[n],_b[n];
//    for(int i=0;i<n;i++)
//    {
//        cin>>_a[i]>>_b[i];
//    }
//    init(n,_a,_b);
//    while(q--)
//    {
//        int32_t _m;
//        cin>>_m;
//        int32_t _k[_m];
//        for(int i=0;i<_m;i++)
//        {
//            cin>>_k[i];
//        }
//        cout<<can(_m,_k)<<"\n";
//    }
//}

Compilation message

teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:113:18: warning: variable 'late' set but not used [-Wunused-but-set-variable]
  113 |         int prev,late,a,b,sum=0;
      |                  ^~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12920 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 2 ms 12976 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 4 ms 12888 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12972 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 2 ms 12892 KB Output is correct
20 Correct 2 ms 12892 KB Output is correct
21 Correct 2 ms 12936 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 2 ms 12892 KB Output is correct
24 Correct 2 ms 12892 KB Output is correct
25 Correct 2 ms 12892 KB Output is correct
26 Correct 2 ms 12892 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 79840 KB Output is correct
2 Correct 109 ms 79952 KB Output is correct
3 Correct 90 ms 79952 KB Output is correct
4 Correct 91 ms 80368 KB Output is correct
5 Correct 65 ms 78636 KB Output is correct
6 Correct 63 ms 78676 KB Output is correct
7 Correct 67 ms 78680 KB Output is correct
8 Correct 67 ms 78672 KB Output is correct
9 Correct 80 ms 79500 KB Output is correct
10 Correct 109 ms 79348 KB Output is correct
11 Correct 69 ms 79100 KB Output is correct
12 Correct 65 ms 79124 KB Output is correct
13 Correct 76 ms 78944 KB Output is correct
14 Correct 79 ms 79820 KB Output is correct
15 Correct 85 ms 79696 KB Output is correct
16 Correct 89 ms 79952 KB Output is correct
17 Correct 69 ms 79440 KB Output is correct
18 Correct 73 ms 79324 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 80468 KB Output is correct
2 Correct 97 ms 80720 KB Output is correct
3 Correct 605 ms 83792 KB Output is correct
4 Correct 90 ms 80468 KB Output is correct
5 Correct 410 ms 78932 KB Output is correct
6 Correct 374 ms 79240 KB Output is correct
7 Correct 68 ms 78928 KB Output is correct
8 Correct 294 ms 78968 KB Output is correct
9 Correct 87 ms 79496 KB Output is correct
10 Correct 325 ms 79560 KB Output is correct
11 Correct 359 ms 79764 KB Output is correct
12 Correct 405 ms 79632 KB Output is correct
13 Correct 546 ms 79812 KB Output is correct
14 Correct 946 ms 82060 KB Output is correct
15 Correct 346 ms 80644 KB Output is correct
16 Correct 357 ms 80696 KB Output is correct
17 Correct 268 ms 80024 KB Output is correct
18 Correct 297 ms 79784 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 632 ms 376784 KB Output is correct
2 Correct 636 ms 373328 KB Output is correct
3 Correct 2859 ms 379184 KB Output is correct
4 Correct 621 ms 373372 KB Output is correct
5 Correct 1253 ms 367076 KB Output is correct
6 Correct 1071 ms 366928 KB Output is correct
7 Correct 351 ms 367100 KB Output is correct
8 Correct 951 ms 367128 KB Output is correct
9 Correct 416 ms 367008 KB Output is correct
10 Correct 990 ms 367048 KB Output is correct
11 Correct 1060 ms 367048 KB Output is correct
12 Correct 1169 ms 367028 KB Output is correct
13 Correct 1932 ms 367532 KB Output is correct
14 Execution timed out 4074 ms 375252 KB Time limit exceeded
15 Halted 0 ms 0 KB -