oj.uz

Submission #952220

# Submission time Handle Problem Language Result Execution time Memory
952220 2024-03-23T09:58:49 Z nghiaaa Teams (IOI15_teams) C++17
13 / 100
 2092 ms 506212 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;
    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;
    }
    newTree->use = newTree->l->use + newTree->r->use;
    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);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13404 KB Output is correct
2 Incorrect 3 ms 13404 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 44 ms 41556 KB Output is correct
2 Correct 45 ms 41556 KB Output is correct
3 Correct 45 ms 41508 KB Output is correct
4 Correct 46 ms 41808 KB Output is correct
5 Correct 27 ms 37720 KB Output is correct
6 Correct 27 ms 37640 KB Output is correct
7 Correct 25 ms 37432 KB Output is correct
8 Correct 26 ms 37460 KB Output is correct
9 Correct 126 ms 102892 KB Output is correct
10 Correct 42 ms 49620 KB Output is correct
11 Correct 27 ms 39380 KB Output is correct
12 Correct 26 ms 37172 KB Output is correct
13 Correct 33 ms 37832 KB Output is correct
14 Correct 35 ms 39380 KB Output is correct
15 Correct 42 ms 41044 KB Output is correct
16 Correct 42 ms 41040 KB Output is correct
17 Correct 33 ms 37980 KB Output is correct
18 Correct 28 ms 37720 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 42320 KB Output is correct
2 Correct 51 ms 42876 KB Output is correct
3 Correct 487 ms 178288 KB Output is correct
4 Correct 47 ms 42068 KB Output is correct
5 Correct 226 ms 102740 KB Output is correct
6 Correct 213 ms 94148 KB Output is correct
7 Correct 31 ms 38480 KB Output is correct
8 Correct 155 ms 80208 KB Output is correct
9 Correct 105 ms 103116 KB Output is correct
10 Correct 126 ms 106300 KB Output is correct
11 Correct 166 ms 135368 KB Output is correct
12 Correct 239 ms 156464 KB Output is correct
13 Correct 418 ms 179212 KB Output is correct
14 Correct 529 ms 191312 KB Output is correct
15 Correct 157 ms 113304 KB Output is correct
16 Incorrect 158 ms 115240 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 160336 KB Output is correct
2 Correct 274 ms 160356 KB Output is correct
3 Correct 1926 ms 469812 KB Output is correct
4 Correct 258 ms 159056 KB Output is correct
5 Correct 1095 ms 287384 KB Output is correct
6 Correct 1025 ms 268508 KB Output is correct
7 Correct 123 ms 138840 KB Output is correct
8 Correct 696 ms 243152 KB Output is correct
9 Correct 571 ms 506212 KB Output is correct
10 Correct 376 ms 325476 KB Output is correct
11 Correct 466 ms 379320 KB Output is correct
12 Correct 680 ms 429064 KB Output is correct
13 Correct 1771 ms 476152 KB Output is correct
14 Correct 2092 ms 503368 KB Output is correct
15 Incorrect 535 ms 329916 KB Output isn't correct
16 Halted 0 ms 0 KB -