oj.uz

Submission #952219

# Submission time Handle Problem Language Result Execution time Memory
952219 2024-03-23T09:57:06 Z nghiaaa Teams (IOI15_teams) C++14
13 / 100
 1907 ms 506048 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 = __;
    }
    else 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 4 ms 13492 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 44 ms 41556 KB Output is correct
3 Correct 45 ms 41600 KB Output is correct
4 Correct 47 ms 41816 KB Output is correct
5 Correct 27 ms 37724 KB Output is correct
6 Correct 26 ms 37468 KB Output is correct
7 Correct 25 ms 37324 KB Output is correct
8 Correct 26 ms 37468 KB Output is correct
9 Correct 108 ms 103104 KB Output is correct
10 Correct 42 ms 49612 KB Output is correct
11 Correct 29 ms 39372 KB Output is correct
12 Correct 25 ms 37136 KB Output is correct
13 Correct 30 ms 37844 KB Output is correct
14 Correct 34 ms 39284 KB Output is correct
15 Correct 43 ms 41244 KB Output is correct
16 Correct 41 ms 41044 KB Output is correct
17 Correct 27 ms 37980 KB Output is correct
18 Correct 30 ms 37808 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 72472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 160080 KB Output is correct
2 Correct 272 ms 160292 KB Output is correct
3 Correct 1907 ms 469640 KB Output is correct
4 Correct 263 ms 159296 KB Output is correct
5 Correct 1020 ms 287060 KB Output is correct
6 Correct 840 ms 268632 KB Output is correct
7 Correct 115 ms 138660 KB Output is correct
8 Correct 815 ms 242904 KB Output is correct
9 Correct 563 ms 506048 KB Output is correct
10 Correct 373 ms 325316 KB Output is correct
11 Correct 458 ms 379332 KB Output is correct
12 Incorrect 676 ms 429140 KB Output isn't correct
13 Halted 0 ms 0 KB -