oj.uz

Submission #952208

# Submission time Handle Problem Language Result Execution time Memory
952208 2024-03-23T09:40:29 Z nghiaaa Teams (IOI15_teams) C++17
0 / 100
 1996 ms 505788 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||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 (lastOfUs > 0) newTree->use = upper_bound(all(arr->tap),lastOfUs)-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= (!lastOfUs)?newTree->preOrder:lastOfUs;
    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: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:72:73: 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);
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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 4 ms 13404 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 13404 KB Output is correct
7 Correct 4 ms 13656 KB Output is correct
8 Correct 4 ms 13656 KB Output is correct
9 Correct 4 ms 13660 KB Output is correct
10 Correct 4 ms 13776 KB Output is correct
11 Correct 3 ms 13404 KB Output is correct
12 Incorrect 5 ms 14428 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 41564 KB Output is correct
2 Correct 44 ms 41556 KB Output is correct
3 Correct 43 ms 41552 KB Output is correct
4 Correct 45 ms 41816 KB Output is correct
5 Correct 29 ms 37712 KB Output is correct
6 Correct 25 ms 37468 KB Output is correct
7 Correct 25 ms 37468 KB Output is correct
8 Correct 25 ms 37460 KB Output is correct
9 Correct 108 ms 101988 KB Output is correct
10 Correct 48 ms 48840 KB Output is correct
11 Correct 26 ms 39124 KB Output is correct
12 Correct 25 ms 37076 KB Output is correct
13 Incorrect 32 ms 37896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 42320 KB Output is correct
2 Correct 55 ms 42836 KB Output is correct
3 Correct 460 ms 152528 KB Output is correct
4 Correct 45 ms 42068 KB Output is correct
5 Correct 203 ms 90052 KB Output is correct
6 Correct 177 ms 83148 KB Output is correct
7 Correct 30 ms 38224 KB Output is correct
8 Correct 142 ms 71836 KB Output is correct
9 Correct 109 ms 102780 KB Output is correct
10 Correct 124 ms 102508 KB Output is correct
11 Correct 160 ms 126408 KB Output is correct
12 Incorrect 241 ms 142980 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 160024 KB Output is correct
2 Correct 259 ms 160080 KB Output is correct
3 Correct 1996 ms 411284 KB Output is correct
4 Correct 253 ms 159056 KB Output is correct
5 Correct 1069 ms 256740 KB Output is correct
6 Correct 976 ms 242060 KB Output is correct
7 Correct 122 ms 138836 KB Output is correct
8 Correct 769 ms 221608 KB Output is correct
9 Correct 602 ms 505788 KB Output is correct
10 Correct 379 ms 312068 KB Output is correct
11 Correct 453 ms 355740 KB Output is correct
12 Incorrect 683 ms 397072 KB Output isn't correct
13 Halted 0 ms 0 KB -