oj.uz

답안 #991073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991073 2024-06-01T08:21:11 Z User0069 팀들 (IOI15_teams) C++17
100 / 100
 3785 ms 163768 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,val[maxn*30],r[maxn*30],l[maxn*30],cur;
struct node
{
    node *l,*r;
    int val;
    node():l(NULL),r(NULL),val(0){};
};
int new_node()
{
    return ++cur;
}
int root[maxn];
vector<int> v[maxn];
int cons(int cl,int cr)
{
    int kk=new_node();
    if(cl==cr)
    {
        return kk;
    }
    int mid=(cl+cr)/2;
    l[kk]=cons(cl,mid);
    r[kk]=cons(mid+1,cr);
    return kk;
}
int update(int kk,int cl,int cr,int pos,int v)
{
    int kkk=new_node();
    l[kkk]=l[kk];
    r[kkk]=r[kk];
    val[kkk]=val[kk];
    if(cl==cr)
    {
        val[kkk]+=v;
        return kkk;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) l[kkk]=update(l[kk],cl,mid,pos,v);
    else r[kkk]=update(r[kk],mid+1,cr,pos,v);
    val[kkk]=val[l[kkk]]+val[r[kkk]];
    return kkk;
}
int get(int kk,int cl,int cr,int L,int R )
{
    if(cl>R||cr<L) return 0;
    if(cl>=L&&cr<=R) return val[kk];
    int mid=(cl+cr)/2;
    return get(l[kk],cl,mid,L,R)+get(r[kk],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(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 'int update(int, int, int, int, int)':
teams.cpp:44:45: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   44 | int update(int kk,int cl,int cr,int pos,int v)
      |                                         ~~~~^
teams.cpp:31:13: note: shadowed declaration is here
   31 | vector<int> v[maxn];
      |             ^
teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:143:13: warning: declaration of 'l' shadows a global declaration [-Wshadow]
  143 |         int l=ra,r=st.back().range,ans=-1;
      |             ^
teams.cpp:19:31: note: shadowed declaration is here
   19 | int N,val[maxn*30],r[maxn*30],l[maxn*30],cur;
      |                               ^
teams.cpp:143:18: warning: declaration of 'r' shadows a global declaration [-Wshadow]
  143 |         int l=ra,r=st.back().range,ans=-1;
      |                  ^
teams.cpp:19:20: note: shadowed declaration is here
   19 | int N,val[maxn*30],r[maxn*30],l[maxn*30],cur;
      |                    ^
teams.cpp:117:18: warning: variable 'late' set but not used [-Wunused-but-set-variable]
  117 |         int prev,late,a,b,sum=0;
      |                  ^~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 40788 KB Output is correct
2 Correct 34 ms 40784 KB Output is correct
3 Correct 36 ms 40712 KB Output is correct
4 Correct 39 ms 41308 KB Output is correct
5 Correct 20 ms 39772 KB Output is correct
6 Correct 20 ms 39768 KB Output is correct
7 Correct 20 ms 39772 KB Output is correct
8 Correct 20 ms 39860 KB Output is correct
9 Correct 38 ms 41680 KB Output is correct
10 Correct 70 ms 41684 KB Output is correct
11 Correct 25 ms 41680 KB Output is correct
12 Correct 20 ms 41684 KB Output is correct
13 Correct 25 ms 39472 KB Output is correct
14 Correct 26 ms 40140 KB Output is correct
15 Correct 33 ms 40788 KB Output is correct
16 Correct 33 ms 40788 KB Output is correct
17 Correct 22 ms 41564 KB Output is correct
18 Correct 22 ms 39516 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 41296 KB Output is correct
2 Correct 43 ms 41216 KB Output is correct
3 Correct 451 ms 44280 KB Output is correct
4 Correct 38 ms 41300 KB Output is correct
5 Correct 421 ms 40016 KB Output is correct
6 Correct 344 ms 40020 KB Output is correct
7 Correct 28 ms 40284 KB Output is correct
8 Correct 270 ms 40280 KB Output is correct
9 Correct 36 ms 41680 KB Output is correct
10 Correct 304 ms 41928 KB Output is correct
11 Correct 386 ms 41932 KB Output is correct
12 Correct 386 ms 42024 KB Output is correct
13 Correct 514 ms 40136 KB Output is correct
14 Correct 582 ms 42852 KB Output is correct
15 Correct 304 ms 41296 KB Output is correct
16 Correct 318 ms 41212 KB Output is correct
17 Correct 246 ms 40032 KB Output is correct
18 Correct 273 ms 39884 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 321 ms 157784 KB Output is correct
2 Correct 300 ms 157776 KB Output is correct
3 Correct 2400 ms 163668 KB Output is correct
4 Correct 293 ms 157780 KB Output is correct
5 Correct 1048 ms 152036 KB Output is correct
6 Correct 883 ms 151856 KB Output is correct
7 Correct 102 ms 151888 KB Output is correct
8 Correct 709 ms 151948 KB Output is correct
9 Correct 194 ms 150684 KB Output is correct
10 Correct 843 ms 150724 KB Output is correct
11 Correct 974 ms 150688 KB Output is correct
12 Correct 1137 ms 150724 KB Output is correct
13 Correct 1528 ms 151748 KB Output is correct
14 Correct 3785 ms 159620 KB Output is correct
15 Correct 997 ms 163536 KB Output is correct
16 Correct 993 ms 163768 KB Output is correct
17 Correct 695 ms 157884 KB Output is correct
18 Correct 719 ms 157980 KB Output is correct