oj.uz

Submission #952202

# Submission time Handle Problem Language Result Execution time Memory
952202 2024-03-23T09:30:33 Z nghiaaa Teams (IOI15_teams) C++17
0 / 100
 1911 ms 411224 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 l = 1,int r = n, IT_tap *arr = tree_tap)
{
    if (r < k||left == 0) return tree;
    int i = upper_bound(all(arr->tap),k)-begin(arr->tap);
    IT *newTree = new IT; *newTree = *tree;
    int mid=(l+r)>>1;
    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;
    if (preOrder > 0)
    {
        newTree->l->preOrder = newTree->r->preOrder = preOrder;
        newTree->l->use = upper_bound(all(arr->l->tap),preOrder)-begin(arr->l->tap);
        newTree->r->use = upper_bound(all(arr->r->tap),preOrder)-begin(arr->r->tap);
        newTree->preOrder = 0;
    }
    IT * __ = get(tree->l,k,left,l,mid,arr->l);
    newTree->l = __;
    if (left) {
        __ = get(tree->r,k,left,mid+1,r,arr->r);
        newTree->r = __;
    }
    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, IT_tap*)':
teams.cpp:69:41: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   69 |     int i = upper_bound(all(arr->tap),k)-begin(arr->tap);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:88:65: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   88 |         newTree->l->use = upper_bound(all(arr->l->tap),preOrder)-begin(arr->l->tap);
      |                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp:89:65: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   89 |         newTree->r->use = upper_bound(all(arr->r->tap),preOrder)-begin(arr->r->tap);
      |                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13400 KB Output is correct
2 Correct 3 ms 13404 KB Output is correct
3 Correct 3 ms 13512 KB Output is correct
4 Correct 3 ms 13660 KB Output is correct
5 Correct 3 ms 13404 KB Output is correct
6 Correct 3 ms 13660 KB Output is correct
7 Correct 4 ms 13660 KB Output is correct
8 Correct 3 ms 13660 KB Output is correct
9 Correct 3 ms 13576 KB Output is correct
10 Incorrect 3 ms 13660 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 41496 KB Output is correct
2 Correct 48 ms 41472 KB Output is correct
3 Correct 45 ms 41556 KB Output is correct
4 Correct 49 ms 41868 KB Output is correct
5 Correct 26 ms 37668 KB Output is correct
6 Correct 27 ms 37460 KB Output is correct
7 Correct 25 ms 37456 KB Output is correct
8 Correct 25 ms 38228 KB Output is correct
9 Correct 105 ms 102808 KB Output is correct
10 Correct 41 ms 49532 KB Output is correct
11 Correct 27 ms 39624 KB Output is correct
12 Correct 25 ms 37844 KB Output is correct
13 Incorrect 31 ms 38860 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 42604 KB Output is correct
2 Correct 50 ms 42580 KB Output is correct
3 Correct 468 ms 152696 KB Output is correct
4 Correct 45 ms 43396 KB Output is correct
5 Correct 199 ms 91100 KB Output is correct
6 Correct 178 ms 84188 KB Output is correct
7 Correct 30 ms 39516 KB Output is correct
8 Incorrect 114 ms 62448 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 159824 KB Output is correct
2 Correct 279 ms 160224 KB Output is correct
3 Correct 1911 ms 411224 KB Output is correct
4 Correct 254 ms 166076 KB Output is correct
5 Correct 1055 ms 261580 KB Output is correct
6 Correct 771 ms 246472 KB Output is correct
7 Correct 127 ms 143384 KB Output is correct
8 Incorrect 563 ms 199088 KB Output isn't correct
9 Halted 0 ms 0 KB -