oj.uz

Submission #898264

# Submission time Handle Problem Language Result Execution time Memory
898264 2024-01-04T12:17:33 Z tolbi Teams (IOI15_teams) C++17
0 / 100
 2242 ms 339352 KB 
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
const int LIMN = 500023;
struct PST{
    struct Node{
        Node* lnode;
        Node* rnode;
        int val, tim;
        Node():rnode(nullptr),lnode(nullptr),val(0),tim(0){}
        Node(Node* nd, int tim):lnode(nd->lnode),rnode(nd->rnode),val(nd->val),tim(tim){}
        Node(int tim):lnode(nullptr),rnode(nullptr),val(0),tim(tim){}
        inline Node* crl(){
            if (lnode==nullptr) lnode=new Node(tim);
            else if (lnode->tim!=tim) lnode=new Node(lnode,tim);
            return lnode;
        }
        inline Node* crr(){
            if (rnode==nullptr) rnode=new Node(tim);
            else if (rnode->tim!=tim) rnode=new Node(rnode,tim);
            return rnode;
        }
    };
    vector<Node*> roots;
    PST(){roots.push_back(new Node());}
    void crl(){
        roots.push_back(new Node(roots.back(), roots.size()));
    }
    void update(int pos, int val){
        int l = 0, r = LIMN;
        Node* nd = roots.back();
        while (l<r){
            int mid = l+(r-l)/2;
            nd->val+=val;
            if (mid>=pos){
                r=mid;
                nd=nd->crl();
            }
            else {
                l=mid+1;
                nd=nd->crr();
            }
        }
        nd->val+=val;
    }
    int query(int tarl, int tarr, int tim, int l = 0, int r = -1, Node* node = nullptr){
        if (r==-1){
            r=LIMN;
            node=roots[tim];
        }
        if (node==nullptr) return 0ll;
        if (l>=tarl && r<=tarr) return node->val;
        if (l>tarr || r<tarl) return 0ll;
        int mid = l+(r-l)/2;
        int lnode = query(tarl, tarr, tim, l, mid, node->lnode);
        int rnode = query(tarl, tarr, tim, mid+1, r, node->rnode);
        return lnode+rnode;
    }
} segtree;

vector<pair<int,int>> arr;
int n;
void init(int N, int A[], int B[]) {
    n=N;
    arr.resize(N);
    for (int i = 0; i < N; ++i)
    {
        arr[i]={A[i],B[i]};
    }
    sort(arr.begin(), arr.end(), [&](pair<int,int> a, pair<int,int> b){
        return a.second<b.second;
    });
    for (int i = 0; i < N; ++i)
    {
        segtree.update(arr[i].first,1);
        if (i!=N-1) segtree.crl();
    }
}
int bsr(int x){
    if (arr.back().second<x) return n;
    int l = 0, r = n-1;
    while (l<r){
        int mid = l+(r-l)/2;
        if (arr[mid].second>=x){
            r=mid;
        }
        else l=mid+1;
    }
    return l;
}
int can(int M, int K[]) {
    sort(K,K+M);
    int crr = 0;
    for (int i = 0; i < M; i++){
        crr=max(crr,bsr(K[i]));
        int cik = 0;
        if (crr>0){
            cik = segtree.query(0,K[i],crr-1);
        }
        if (segtree.query(0,K[i],n-1)-cik<K[i]) return 0;
        int l = crr, r = n-1;
        while (l<r){
            int mid = l+(r-l)/2;
            if (segtree.query(0,K[i],mid)-cik<K[i]){
                l=mid+1;
            }
            else r=mid;
        }
        crr=l+1;
    }
    return true;
}

Compilation message

teams.cpp: In constructor 'PST::Node::Node()':
teams.cpp:8:15: warning: 'PST::Node::rnode' will be initialized after [-Wreorder]
    8 |         Node* rnode;
      |               ^~~~~
teams.cpp:7:15: warning:   'PST::Node* PST::Node::lnode' [-Wreorder]
    7 |         Node* lnode;
      |               ^~~~~
teams.cpp:10:9: warning:   when initialized here [-Wreorder]
   10 |         Node():rnode(nullptr),lnode(nullptr),val(0),tim(0){}
      |         ^~~~
teams.cpp: In constructor 'PST::Node::Node(PST::Node*, int)':
teams.cpp:11:28: warning: declaration of 'tim' shadows a member of 'PST::Node' [-Wshadow]
   11 |         Node(Node* nd, int tim):lnode(nd->lnode),rnode(nd->rnode),val(nd->val),tim(tim){}
      |                        ~~~~^~~
teams.cpp:9:18: note: shadowed declaration is here
    9 |         int val, tim;
      |                  ^~~
teams.cpp: In constructor 'PST::Node::Node(PST::Node*, int)':
teams.cpp:11:28: warning: declaration of 'tim' shadows a member of 'PST::Node' [-Wshadow]
   11 |         Node(Node* nd, int tim):lnode(nd->lnode),rnode(nd->rnode),val(nd->val),tim(tim){}
      |                        ~~~~^~~
teams.cpp:9:18: note: shadowed declaration is here
    9 |         int val, tim;
      |                  ^~~
teams.cpp: In constructor 'PST::Node::Node(PST::Node*, int)':
teams.cpp:11:28: warning: declaration of 'tim' shadows a member of 'PST::Node' [-Wshadow]
   11 |         Node(Node* nd, int tim):lnode(nd->lnode),rnode(nd->rnode),val(nd->val),tim(tim){}
      |                        ~~~~^~~
teams.cpp:9:18: note: shadowed declaration is here
    9 |         int val, tim;
      |                  ^~~
teams.cpp: In constructor 'PST::Node::Node(int)':
teams.cpp:12:18: warning: declaration of 'tim' shadows a member of 'PST::Node' [-Wshadow]
   12 |         Node(int tim):lnode(nullptr),rnode(nullptr),val(0),tim(tim){}
      |              ~~~~^~~
teams.cpp:9:18: note: shadowed declaration is here
    9 |         int val, tim;
      |                  ^~~
teams.cpp: In constructor 'PST::Node::Node(int)':
teams.cpp:12:18: warning: declaration of 'tim' shadows a member of 'PST::Node' [-Wshadow]
   12 |         Node(int tim):lnode(nullptr),rnode(nullptr),val(0),tim(tim){}
      |              ~~~~^~~
teams.cpp:9:18: note: shadowed declaration is here
    9 |         int val, tim;
      |                  ^~~
teams.cpp: In constructor 'PST::Node::Node(int)':
teams.cpp:12:18: warning: declaration of 'tim' shadows a member of 'PST::Node' [-Wshadow]
   12 |         Node(int tim):lnode(nullptr),rnode(nullptr),val(0),tim(tim){}
      |              ~~~~^~~
teams.cpp:9:18: note: shadowed declaration is here
    9 |         int val, tim;
      |                  ^~~
teams.cpp: In member function 'void PST::crl()':
teams.cpp:27:58: warning: conversion from 'std::vector<PST::Node*>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   27 |         roots.push_back(new Node(roots.back(), roots.size()));
      |                                                ~~~~~~~~~~^~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 3 ms 344 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 65016 KB Output is correct
2 Correct 100 ms 65220 KB Output is correct
3 Correct 82 ms 66388 KB Output is correct
4 Correct 84 ms 66780 KB Output is correct
5 Correct 73 ms 66260 KB Output is correct
6 Correct 69 ms 65988 KB Output is correct
7 Correct 64 ms 65940 KB Output is correct
8 Correct 64 ms 66036 KB Output is correct
9 Correct 134 ms 66384 KB Output is correct
10 Incorrect 116 ms 66104 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 65440 KB Output is correct
2 Correct 89 ms 65476 KB Output is correct
3 Correct 579 ms 70428 KB Output is correct
4 Correct 83 ms 66976 KB Output is correct
5 Correct 296 ms 66748 KB Output is correct
6 Correct 276 ms 66668 KB Output is correct
7 Correct 79 ms 66548 KB Output is correct
8 Correct 222 ms 66992 KB Output is correct
9 Correct 134 ms 66524 KB Output is correct
10 Incorrect 351 ms 66500 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 325100 KB Output is correct
2 Correct 545 ms 332808 KB Output is correct
3 Correct 2242 ms 339352 KB Output is correct
4 Correct 510 ms 332132 KB Output is correct
5 Correct 1858 ms 330152 KB Output is correct
6 Correct 1607 ms 330064 KB Output is correct
7 Correct 331 ms 329912 KB Output is correct
8 Correct 1444 ms 330388 KB Output is correct
9 Correct 836 ms 330680 KB Output is correct
10 Incorrect 1361 ms 329148 KB Output isn't correct
11 Halted 0 ms 0 KB -