oj.uz

Submission #990619

# Submission time Handle Problem Language Result Execution time Memory
990619 2024-05-30T17:33:10 Z User0069 Teams (IOI15_teams) C++17
13 / 100
 998 ms 380012 KB 
#include<bits/stdc++.h>
#include"teams.h"
#define taskname ""
#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)-get(root[a-1],0,N,c,d);
}
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];
}
int32_t can(int32_t m,int32_t* k)
{
    int sum=0;
    int need=0;
    int borrow=0,prev,late;
    sort(k,k+m);
    for(int i=0;i<m;i++)
    {
        if(i==0) prev=0;
        else prev=k[i-1];
        if(i==m-1) late=N+1;
        else late=k[i+1];
        int lmao=cnt(k[i],late-1,prev+1,k[i]);
        sum+=cnt(k[i],N,prev+1,k[i]);
        sum-=max(lmao,1LL*k[i]);
        if(sum<0) return 0;
    }
    return 1;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname".OUT","w",stdout);
//    }
//    Faster
//}

Compilation message

teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:89:9: warning: unused variable 'need' [-Wunused-variable]
   89 |     int need=0;
      |         ^~~~
teams.cpp:90:9: warning: unused variable 'borrow' [-Wunused-variable]
   90 |     int borrow=0,prev,late;
      |         ^~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory 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 2 ms 12928 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Incorrect 2 ms 12892 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 79972 KB Output is correct
2 Correct 93 ms 79956 KB Output is correct
3 Correct 91 ms 79956 KB Output is correct
4 Correct 95 ms 80700 KB Output is correct
5 Correct 64 ms 79208 KB Output is correct
6 Correct 64 ms 79116 KB Output is correct
7 Correct 72 ms 79236 KB Output is correct
8 Correct 64 ms 79188 KB Output is correct
9 Correct 72 ms 80068 KB Output is correct
10 Correct 68 ms 79556 KB Output is correct
11 Correct 70 ms 79612 KB Output is correct
12 Correct 65 ms 79752 KB Output is correct
13 Correct 77 ms 79556 KB Output is correct
14 Correct 78 ms 80324 KB Output is correct
15 Correct 88 ms 80364 KB Output is correct
16 Correct 93 ms 80556 KB Output is correct
17 Correct 67 ms 80136 KB Output is correct
18 Correct 67 ms 79820 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 80720 KB Output is correct
2 Correct 97 ms 80548 KB Output is correct
3 Correct 214 ms 83792 KB Output is correct
4 Correct 91 ms 80716 KB Output is correct
5 Correct 96 ms 79696 KB Output is correct
6 Correct 96 ms 79696 KB Output is correct
7 Correct 70 ms 79540 KB Output is correct
8 Correct 89 ms 79588 KB Output is correct
9 Correct 72 ms 80068 KB Output is correct
10 Correct 89 ms 80072 KB Output is correct
11 Correct 91 ms 80324 KB Output is correct
12 Correct 106 ms 80348 KB Output is correct
13 Incorrect 152 ms 80580 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 377680 KB Output is correct
2 Correct 613 ms 374372 KB Output is correct
3 Correct 998 ms 380012 KB Output is correct
4 Correct 586 ms 374116 KB Output is correct
5 Correct 411 ms 369748 KB Output is correct
6 Correct 405 ms 369772 KB Output is correct
7 Correct 324 ms 369744 KB Output is correct
8 Correct 375 ms 369744 KB Output is correct
9 Correct 352 ms 368828 KB Output is correct
10 Correct 379 ms 372172 KB Output is correct
11 Correct 377 ms 372676 KB Output is correct
12 Correct 456 ms 373440 KB Output is correct
13 Incorrect 578 ms 375560 KB Output isn't correct
14 Halted 0 ms 0 KB -