Submission #898264

#	Time	Username	Problem	Language	Result	Execution time	Memory
898264		tolbi	Teams (IOI15_teams)	C++17	0 / 100	2242 ms	339352 KiB

teams

#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 (stderr)

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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23