oj.uz

Submission #990623

# Submission time Handle Problem Language Result Execution time Memory
990623 2024-05-30T17:51:06 Z User0069 Teams (IOI15_teams) C++17
0 / 100
 1025 ms 380240 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);
    vector<pii> vv;
    int cur=k[0];
    int num=0;
    for(int i=1;i<m;i++)
    {
        if(k[i]!=cur)
        {
            vv.push_back({cur,cur*num});
            cur=k[i];
            num=1;
        }
        else num++;
    }
    vv.push_back({cur,cur*num});
    for(int i=0;i<vv.size();i++)
    {
        if(i==0) prev=0;
        else prev=vv[i-1].fi;
        if(i==vv.size()-1) late=N+1;
        else late=vv[i+1].fi;
        int lmao=cnt(vv[i].fi,late-1,prev+1,vv[i].fi);
        sum+=cnt(vv[i].fi,N,prev+1,vv[i].fi);
        sum-=max(lmao,vv[i].sc);
        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:106:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0;i<vv.size();i++)
      |                 ~^~~~~~~~~~
teams.cpp:110:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if(i==vv.size()-1) late=N+1;
      |            ~^~~~~~~~~~~~~
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 Incorrect 2 ms 12888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 79368 KB Output is correct
2 Correct 97 ms 79272 KB Output is correct
3 Incorrect 92 ms 79188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 79700 KB Output is correct
2 Correct 96 ms 79700 KB Output is correct
3 Incorrect 219 ms 82768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 374352 KB Output is correct
2 Correct 597 ms 374384 KB Output is correct
3 Incorrect 1025 ms 380240 KB Output isn't correct
4 Halted 0 ms 0 KB -