oj.uz

답안 #952210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
952210 2024-03-23T09:45:43 Z nghiaaa 팀들 (IOI15_teams) C++17
13 / 100
 2129 ms 503424 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 13404 KB Output is correct
2 Correct 3 ms 13404 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13656 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 13660 KB Output is correct
8 Correct 3 ms 13660 KB Output is correct
9 Correct 4 ms 13660 KB Output is correct
10 Correct 3 ms 13660 KB Output is correct
11 Correct 3 ms 13404 KB Output is correct
12 Correct 4 ms 14424 KB Output is correct
13 Correct 4 ms 14172 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Incorrect 3 ms 13660 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 41560 KB Output is correct
2 Correct 44 ms 41656 KB Output is correct
3 Correct 43 ms 41552 KB Output is correct
4 Correct 45 ms 41992 KB Output is correct
5 Correct 25 ms 37724 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 37468 KB Output is correct
9 Correct 104 ms 102056 KB Output is correct
10 Correct 45 ms 48844 KB Output is correct
11 Correct 26 ms 39116 KB Output is correct
12 Correct 25 ms 37076 KB Output is correct
13 Correct 31 ms 37836 KB Output is correct
14 Correct 34 ms 40404 KB Output is correct
15 Correct 40 ms 42184 KB Output is correct
16 Correct 41 ms 42320 KB Output is correct
17 Correct 27 ms 38992 KB Output is correct
18 Correct 28 ms 38992 KB Output is correct

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 42320 KB Output is correct
2 Correct 58 ms 42676 KB Output is correct
3 Correct 481 ms 152624 KB Output is correct
4 Correct 45 ms 41848 KB Output is correct
5 Correct 202 ms 89880 KB Output is correct
6 Correct 181 ms 82992 KB Output is correct
7 Correct 30 ms 38228 KB Output is correct
8 Correct 141 ms 71764 KB Output is correct
9 Correct 106 ms 102260 KB Output is correct
10 Correct 123 ms 101836 KB Output is correct
11 Correct 163 ms 125640 KB Output is correct
12 Correct 239 ms 142104 KB Output is correct
13 Correct 417 ms 160720 KB Output is correct
14 Correct 537 ms 168504 KB Output is correct
15 Correct 151 ms 106692 KB Output is correct
16 Incorrect 154 ms 108464 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 160040 KB Output is correct
2 Correct 265 ms 160080 KB Output is correct
3 Correct 2023 ms 411208 KB Output is correct
4 Correct 264 ms 163144 KB Output is correct
5 Correct 1111 ms 259456 KB Output is correct
6 Correct 777 ms 244560 KB Output is correct
7 Correct 124 ms 141144 KB Output is correct
8 Correct 689 ms 224084 KB Output is correct
9 Correct 612 ms 503424 KB Output is correct
10 Correct 401 ms 311000 KB Output is correct
11 Correct 465 ms 354240 KB Output is correct
12 Correct 694 ms 394900 KB Output is correct
13 Correct 1842 ms 432396 KB Output is correct
14 Correct 2129 ms 450256 KB Output is correct
15 Incorrect 535 ms 310508 KB Output isn't correct
16 Halted 0 ms 0 KB -