Submission #434508

#	Time	Username	Problem	Language	Result	Execution time	Memory
434508		qwerasdfzxcl	Teams (IOI15_teams)	C++14	100 / 100	2481 ms	376656 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef long long ll;
int N;
struct Node{
    int x, i;
    Node* l; Node* r;
    Node(){x = i = 0, l = r = nullptr;}
};
Node* root[500500];
int tree[1048577], lazy2[1048577];
bool lazy[1048577];

void build(Node* node, int s, int e){
    if (s==e){
        node->x = 0; return;
    }
    int m = (s+e)>>1;
    node->l = new Node(); node->r = new Node();
    node->l->i = node->i*2, node->r->i = node->i*2+1;
    build(node->l, s, m); build(node->r, m+1, e);
    node->x = 0;
}

void add(Node* prv, Node* now, int s, int e, int x, int v){
    if (s==e){now->x = prv->x+v; return;}
    int m = (s+e)>>1;
    if (x<=m){
        now->l = new Node(); now->l->i = now->i*2;
        now->r = prv->r;
        add(prv->l, now->l, s, m, x, v);
    }
    else{
        now->l = prv->l;
        now->r = new Node(); now->r->i = now->i*2+1;
        add(prv->r, now->r, m+1, e, x, v);
    }
    now->x = now->l->x + now->r->x;
}

int _find(Node* node, int l, int r, int s, int e){
    if (r<s || e<l) return 0;
    if (s<=l && r<=e) {assert(s==l && r==e); return node->x;}
    int m = (l+r)>>1;
    return _find(node->l, l, m, s, e) + _find(node->r, m+1, r, s, e);
}

void propagate(int i, int l, int r){
    if (!lazy[i]) return;
    if (lazy2[i]==-1) tree[i] = 0;
    else tree[i] = _find(root[lazy2[i]], 1, N, l, r);
    if (l!=r){
        lazy[i<<1] = lazy[i], lazy2[i<<1] = lazy2[i];
        lazy[i<<1|1] = lazy[i], lazy2[i<<1|1] = lazy2[i];
    }
    lazy[i] = 0, lazy2[i] = 0;
}

void update(Node* node, int l, int r, int s, int e, int idx){
    propagate(node->i, l, r);
    if (r<s || e<l) return;
    if (s<=l && r<=e){
        lazy[node->i] = 1;
        lazy2[node->i] = idx;
        propagate(node->i, l, r);
        return;
    }
    int m = (l+r)>>1;
    update(node->l, l, m, s, e, idx); update(node->r, m+1, r, s, e, idx);
    tree[node->i] = tree[node->i*2]+tree[node->i*2+1];
}

int XX;
pair<int, int> _lower_bound(Node* node, int l, int r, int e, int k){
    propagate(node->i, l, r);
    if (e<l) return {-1e9, 0};
    if (r<=e && node->x - tree[node->i]<k) return {-1e9, node->x - tree[node->i]};
    if (l==r){
        XX = k;
        return {l, node->x - tree[node->i]};
    }
    int m = (l+r)>>1;
    auto p1 = _lower_bound(node->r, m+1, r, e, k);
    if (p1.first!=-1e9) return p1;
    k -= p1.second;
    auto p2 = _lower_bound(node->l, l, m, e, k);
    if (p2.first!=-1e9) return make_pair(p2.first, p2.second+p1.second);
    return make_pair(-1e9, p2.second+p1.second);
}

void updatep(int i, int l, int r, int x, int val){
    propagate(i, l, r);
    if (r<x || x<l) return;
    if (l==r) {tree[i] += val; return;}
    int m = (l+r)>>1;
    updatep(i<<1, l, m, x, val); updatep(i<<1|1, m+1, r, x, val);
    tree[i] = tree[i<<1] + tree[i<<1|1];
}

bool cmp(pair<int, int> x1, pair<int, int> x2){
    if (x1.second==x2.second) return x1.first<x2.first;
    return x1.second>x2.second;
}

vector<pair<int, int>> v;
void init(int n, int A[], int B[]) {
    N = n;
    root[0] = new Node();
    root[0]->i = 1;
    build(root[0], 1, n);
    v.resize(n);
    for (int i=0;i<n;i++) v[i] = {A[i], B[i]};
    sort(v.begin(), v.end(), cmp);
    for (int i=0;i<n;i++){
        root[i+1] = new Node();
        root[i+1]->i = 1;
        add(root[i], root[i+1], 1, n, v[i].first, 1);
    }
}

int can(int M, int K[]) {
    //printf("\n");
    int s = 0;
    for (int i=0;i<M;i++) s += K[i];
    if (s>N) return 0;
    sort(K, K+M, greater<int>());
    update(root[0], 1, N, 1, N, -1);
    //printf("%d\n", _find(root[4], 1, N, 2, 2));
    for (int i=0;i<M;i++){
        int idx = upper_bound(v.begin(), v.end(), make_pair(1e9, K[i]), cmp) - v.begin();
        //printf("%d: %d\n", i, idx);
        auto p = _lower_bound(root[idx], 1, N, K[i], K[i]);
        //printf("%d %d %d\n", p.first, p.second, XX);
        if (p.first==-1e9) return 0;
        if (p.first+1<=K[i]) update(root[idx], 1, N, p.first+1, K[i], idx);
        updatep(1, 1, N, p.first, XX);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:134:78: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  134 |         int idx = upper_bound(v.begin(), v.end(), make_pair(1e9, K[i]), cmp) - v.begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23