oj.uz

Submission #952235

# Submission time Handle Problem Language Result Execution time Memory
952235 2024-03-23T10:32:40 Z nghiaaa Teams (IOI15_teams) C++17
100 / 100
 1595 ms 500908 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)
{
    if (r < k) return nullptr;
    int mid=(l+r)>>1;
    if (l>=k){
        IT *newTree = new IT; *newTree = *tree;
        if (lastOfUs > 0) newTree->use = upper_bound(all(arr->tap),lastOfUs)-begin(arr->tap), newTree->preOrder = lastOfUs;
        if (left == 0) return newTree;
        int i = upper_bound(all(arr->tap),k)-begin(arr->tap);
        if (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;
        IT * __ = get(tree->l,k,left,preOrder,l,mid,arr->l);
        newTree->l = __;

        __ = get(tree->r,k,left,preOrder,mid+1,r,arr->r);
        newTree->r = __;

        newTree->preOrder = 0;
        newTree->use = newTree->l->use + newTree->r->use;
        return newTree;
    }
    else{
        IT *newTree = new IT; *newTree = *tree;
        if (lastOfUs > 0) newTree->preOrder = lastOfUs;
        if (left == 0) return newTree;
        int preOrder= newTree->preOrder;
        IT * __ = get(tree->l,k,left,preOrder,l,mid,arr->l);
        newTree->l = __;

        __ = get(tree->r,k,left,preOrder,mid+1,r,arr->r);
        newTree->r = __;

        newTree->preOrder = 0;
        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:72:77: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   72 |         if (lastOfUs > 0) newTree->use = upper_bound(all(arr->tap),lastOfUs)-begin(arr->tap), newTree->preOrder = lastOfUs;
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:74:45: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   74 |         int i = upper_bound(all(arr->tap),k)-begin(arr->tap);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13404 KB Output is correct
2 Correct 3 ms 13404 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 4 ms 13404 KB Output is correct
6 Correct 3 ms 13404 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 3 ms 13660 KB Output is correct
9 Correct 3 ms 13660 KB Output is correct
10 Correct 3 ms 13828 KB Output is correct
11 Correct 3 ms 13404 KB Output is correct
12 Correct 5 ms 15196 KB Output is correct
13 Correct 4 ms 14172 KB Output is correct
14 Correct 4 ms 13916 KB Output is correct
15 Correct 4 ms 13660 KB Output is correct
16 Correct 3 ms 13660 KB Output is correct
17 Correct 4 ms 13916 KB Output is correct
18 Correct 3 ms 13660 KB Output is correct
19 Correct 3 ms 13660 KB Output is correct
20 Correct 3 ms 13660 KB Output is correct
21 Correct 5 ms 13760 KB Output is correct
22 Correct 3 ms 13660 KB Output is correct
23 Correct 3 ms 13704 KB Output is correct
24 Correct 3 ms 13660 KB Output is correct
25 Correct 3 ms 13660 KB Output is correct
26 Correct 3 ms 13660 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 41532 KB Output is correct
2 Correct 43 ms 41556 KB Output is correct
3 Correct 45 ms 41556 KB Output is correct
4 Correct 46 ms 41812 KB Output is correct
5 Correct 25 ms 37716 KB Output is correct
6 Correct 25 ms 37716 KB Output is correct
7 Correct 24 ms 37456 KB Output is correct
8 Correct 25 ms 37468 KB Output is correct
9 Correct 100 ms 102004 KB Output is correct
10 Correct 43 ms 56784 KB Output is correct
11 Correct 28 ms 40112 KB Output is correct
12 Correct 25 ms 37332 KB Output is correct
13 Correct 31 ms 37844 KB Output is correct
14 Correct 33 ms 39380 KB Output is correct
15 Correct 41 ms 41044 KB Output is correct
16 Correct 41 ms 41040 KB Output is correct
17 Correct 27 ms 37968 KB Output is correct
18 Correct 28 ms 37972 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 42320 KB Output is correct
2 Correct 50 ms 42832 KB Output is correct
3 Correct 373 ms 164256 KB Output is correct
4 Correct 46 ms 41812 KB Output is correct
5 Correct 120 ms 126288 KB Output is correct
6 Correct 108 ms 114548 KB Output is correct
7 Correct 32 ms 38748 KB Output is correct
8 Correct 91 ms 95368 KB Output is correct
9 Correct 96 ms 101916 KB Output is correct
10 Correct 133 ms 145864 KB Output is correct
11 Correct 175 ms 172572 KB Output is correct
12 Correct 220 ms 176376 KB Output is correct
13 Correct 334 ms 191804 KB Output is correct
14 Correct 437 ms 181116 KB Output is correct
15 Correct 146 ms 133204 KB Output is correct
16 Correct 156 ms 136584 KB Output is correct
17 Correct 119 ms 114240 KB Output is correct
18 Correct 142 ms 130916 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 159828 KB Output is correct
2 Correct 271 ms 160080 KB Output is correct
3 Correct 1384 ms 437208 KB Output is correct
4 Correct 276 ms 159200 KB Output is correct
5 Correct 333 ms 338768 KB Output is correct
6 Correct 315 ms 313532 KB Output is correct
7 Correct 118 ms 138872 KB Output is correct
8 Correct 264 ms 279120 KB Output is correct
9 Correct 548 ms 500908 KB Output is correct
10 Correct 393 ms 409284 KB Output is correct
11 Correct 472 ms 452228 KB Output is correct
12 Correct 624 ms 473300 KB Output is correct
13 Correct 1272 ms 493484 KB Output is correct
14 Correct 1595 ms 475664 KB Output is correct
15 Correct 479 ms 365476 KB Output is correct
16 Correct 476 ms 372428 KB Output is correct
17 Correct 358 ms 338720 KB Output is correct
18 Correct 343 ms 327996 KB Output is correct