oj.uz

Submission #952227

# Submission time Handle Problem Language Result Execution time Memory
952227 2024-03-23T10:10:46 Z nghiaaa Teams (IOI15_teams) C++17
13 / 100
 2148 ms 506256 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define endl "\n"
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define forw2(i,j,z,k) for(int i=(int)j;i<=(int)z;i+=k)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define ford2(i,j,z,k) for (int i=(int)j;i>=(int)z;i-=k)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
const ll inf=(ll)1<<60;
const int N=5e5;
const int Q=2e5;
int n;
vector<int> DS[N+1];
struct IT_tap{
    IT_tap *l= nullptr;
    IT_tap *r= nullptr;
    vector<int> tap;
    IT_tap():l(nullptr),r(nullptr){}
    IT_tap(IT_tap *L, IT_tap *R):l(L),r(R){}
    IT_tap(IT_tap *L, IT_tap *R,vector<int> &u):l(L),r(R),tap(u){}
};
IT_tap * tree_tap=new IT_tap();
struct IT{
    IT *l= nullptr;
    IT *r= nullptr;
    int use=0,preOrder=0;
    IT():l(nullptr),r(nullptr){}
    IT(IT *L, IT *R):l(L),r(R){}
};
IT *version[Q+10];
IT *build(int l = 1,int r = n, IT_tap *tree = tree_tap)
{
    if (l==r){
        sort(all(DS[l]));
        tree->tap = DS[l];
        return new IT(nullptr,nullptr);
    }
    int mid=(l+r)>>1;
    tree->l=new IT_tap;
    tree->r=new IT_tap;
    IT * tmp= new IT(build(l,mid,tree->l),build(mid+1,r,tree->r));
    tree->tap.assign(sz(tree->l->tap)+sz(tree->r->tap),0);
    merge(all(tree->l->tap),all(tree->r->tap),begin(tree->tap));
    return tmp;
}
void init(int _n,int A[],int B[])
{
    n=_n;
    forw(i,0,n-1){
        DS[B[i]].push_back(A[i]);
    }
    version[0]=build();
}
IT *get(IT *tree,int k,int &left,int lastOfUs = 0,int l = 1,int r = n, IT_tap *arr = tree_tap)
{
    IT *newTree = new IT; *newTree = *tree;
    int mid=(l+r)>>1;
    if (lastOfUs > 0) newTree->use = upper_bound(all(arr->tap),lastOfUs)-begin(arr->tap), newTree->preOrder = lastOfUs;
    if (r < k||left == 0) return newTree;
    int i = upper_bound(all(arr->tap),k)-begin(arr->tap);
    if (l>=k&&i - newTree->use <= left)
    {
        left -= (i - newTree-> use);
        newTree->use = i ;
        newTree->preOrder = k;
        return newTree;
    }
    else if (l==r){
        newTree->use += left;
        left = 0;
        return newTree;
    }
    int preOrder= newTree->preOrder;
    int _r ;
    IT * __ = get(tree->l,k,left,preOrder,l,mid,arr->l);
    newTree->l = __;
    if (left){
        __ = get(tree->r,k,left,preOrder,mid+1,r,arr->r);
        newTree->r = __;
        newTree->preOrder = 0;
        _r = newTree->r->use;
    }
    else _r = preOrder?upper_bound(all(arr->r->tap),preOrder)-begin(arr->r->tap):newTree->r->use;
    newTree->use = newTree->l->use + _r;
    return newTree;
}
int can(int m,int query[])
{
    sort(query,query+m);
    forw(i,0,m-1){
        int k=query[i];
        IT * _=get(version[i],query[i],k);
        version[i+1]=_;
        if (k>0) return 0;
    }
    return 1;
}

Compilation message

teams.cpp: In function 'IT* get(IT*, int, int&, int, int, int, IT_tap*)':
teams.cpp:70:73: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   70 |     if (lastOfUs > 0) newTree->use = upper_bound(all(arr->tap),lastOfUs)-begin(arr->tap), newTree->preOrder = lastOfUs;
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:72:41: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   72 |     int i = upper_bound(all(arr->tap),k)-begin(arr->tap);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:95:23: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   95 |     else _r = preOrder?upper_bound(all(arr->r->tap),preOrder)-begin(arr->r->tap):newTree->r->use;
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13400 KB Output is correct
2 Incorrect 3 ms 13656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 41524 KB Output is correct
2 Correct 54 ms 41488 KB Output is correct
3 Correct 58 ms 41552 KB Output is correct
4 Correct 49 ms 41812 KB Output is correct
5 Correct 29 ms 37716 KB Output is correct
6 Correct 33 ms 37500 KB Output is correct
7 Correct 34 ms 37468 KB Output is correct
8 Correct 25 ms 37356 KB Output is correct
9 Correct 109 ms 103092 KB Output is correct
10 Correct 43 ms 49608 KB Output is correct
11 Correct 27 ms 39376 KB Output is correct
12 Correct 26 ms 37332 KB Output is correct
13 Correct 32 ms 37832 KB Output is correct
14 Correct 45 ms 39372 KB Output is correct
15 Correct 44 ms 41044 KB Output is correct
16 Correct 41 ms 41240 KB Output is correct
17 Correct 29 ms 37980 KB Output is correct
18 Correct 29 ms 37716 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 42320 KB Output is correct
2 Correct 55 ms 43208 KB Output is correct
3 Correct 523 ms 177964 KB Output is correct
4 Correct 50 ms 41924 KB Output is correct
5 Correct 234 ms 102808 KB Output is correct
6 Correct 208 ms 94276 KB Output is correct
7 Correct 33 ms 38360 KB Output is correct
8 Correct 158 ms 80220 KB Output is correct
9 Correct 112 ms 103116 KB Output is correct
10 Correct 134 ms 106248 KB Output is correct
11 Correct 180 ms 135368 KB Output is correct
12 Correct 250 ms 156524 KB Output is correct
13 Correct 455 ms 178936 KB Output is correct
14 Correct 585 ms 191396 KB Output is correct
15 Correct 167 ms 113292 KB Output is correct
16 Correct 164 ms 115304 KB Output is correct
17 Incorrect 153 ms 102740 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 159828 KB Output is correct
2 Correct 287 ms 160080 KB Output is correct
3 Correct 2016 ms 469696 KB Output is correct
4 Correct 294 ms 159172 KB Output is correct
5 Correct 1258 ms 287284 KB Output is correct
6 Correct 1012 ms 268492 KB Output is correct
7 Correct 122 ms 138832 KB Output is correct
8 Correct 911 ms 243072 KB Output is correct
9 Correct 641 ms 506256 KB Output is correct
10 Correct 407 ms 325288 KB Output is correct
11 Correct 521 ms 379280 KB Output is correct
12 Correct 722 ms 429084 KB Output is correct
13 Correct 1845 ms 473068 KB Output is correct
14 Correct 2148 ms 499544 KB Output is correct
15 Incorrect 541 ms 325828 KB Output isn't correct
16 Halted 0 ms 0 KB -