oj.uz

답안 #952222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
952222 2024-03-23T10:04:03 Z nghiaaa 팀들 (IOI15_teams) C++17
13 / 100
 2071 ms 506532 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;
    int _r ;
    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;
        _r = newTree->r->use;
    }
    else _r = upper_bound(all(arr->r->tap),preOrder)-begin(arr->r->tap);
    newTree->use = newTree->l->use + _r;
    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);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:95:53: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   95 |     else _r = upper_bound(all(arr->r->tap),preOrder)-begin(arr->r->tap);
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 13404 KB Output is correct
2 Incorrect 4 ms 13508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 41564 KB Output is correct
2 Correct 44 ms 41552 KB Output is correct
3 Correct 49 ms 41560 KB Output is correct
4 Correct 46 ms 41808 KB Output is correct
5 Correct 26 ms 37724 KB Output is correct
6 Correct 25 ms 37468 KB Output is correct
7 Correct 26 ms 37464 KB Output is correct
8 Correct 24 ms 37468 KB Output is correct
9 Correct 106 ms 103000 KB Output is correct
10 Correct 42 ms 49620 KB Output is correct
11 Correct 27 ms 39424 KB Output is correct
12 Correct 25 ms 37320 KB Output is correct
13 Correct 30 ms 38092 KB Output is correct
14 Correct 35 ms 39440 KB Output is correct
15 Correct 44 ms 41044 KB Output is correct
16 Correct 44 ms 41040 KB Output is correct
17 Correct 28 ms 37980 KB Output is correct
18 Correct 28 ms 37808 KB Output is correct

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 42324 KB Output is correct
2 Correct 51 ms 42836 KB Output is correct
3 Correct 498 ms 178588 KB Output is correct
4 Correct 48 ms 42064 KB Output is correct
5 Correct 248 ms 102636 KB Output is correct
6 Correct 208 ms 94296 KB Output is correct
7 Correct 30 ms 38224 KB Output is correct
8 Correct 157 ms 80304 KB Output is correct
9 Correct 108 ms 103428 KB Output is correct
10 Correct 125 ms 106440 KB Output is correct
11 Correct 167 ms 135372 KB Output is correct
12 Correct 236 ms 156620 KB Output is correct
13 Correct 411 ms 178888 KB Output is correct
14 Correct 549 ms 191600 KB Output is correct
15 Correct 163 ms 113284 KB Output is correct
16 Incorrect 164 ms 115248 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 159976 KB Output is correct
2 Correct 270 ms 160080 KB Output is correct
3 Correct 1971 ms 469888 KB Output is correct
4 Correct 280 ms 159200 KB Output is correct
5 Correct 997 ms 287348 KB Output is correct
6 Correct 902 ms 268584 KB Output is correct
7 Correct 120 ms 138832 KB Output is correct
8 Correct 778 ms 242944 KB Output is correct
9 Correct 586 ms 506532 KB Output is correct
10 Correct 378 ms 325316 KB Output is correct
11 Correct 463 ms 379372 KB Output is correct
12 Correct 670 ms 429252 KB Output is correct
13 Correct 1781 ms 473200 KB Output is correct
14 Correct 2071 ms 499404 KB Output is correct
15 Incorrect 555 ms 325772 KB Output isn't correct
16 Halted 0 ms 0 KB -