oj.uz

Submission #434508

# Submission time Handle Problem Language Result Execution time Memory
434508 2021-06-21T11:24:41 Z qwerasdfzxcl Teams (IOI15_teams) C++14
100 / 100
 2481 ms 376656 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 268 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 64404 KB Output is correct
2 Correct 164 ms 64356 KB Output is correct
3 Correct 161 ms 64336 KB Output is correct
4 Correct 180 ms 64712 KB Output is correct
5 Correct 111 ms 64332 KB Output is correct
6 Correct 108 ms 64316 KB Output is correct
7 Correct 111 ms 64292 KB Output is correct
8 Correct 119 ms 64392 KB Output is correct
9 Correct 169 ms 65508 KB Output is correct
10 Correct 117 ms 65348 KB Output is correct
11 Correct 105 ms 65348 KB Output is correct
12 Correct 120 ms 65268 KB Output is correct
13 Correct 128 ms 64832 KB Output is correct
14 Correct 115 ms 65988 KB Output is correct
15 Correct 148 ms 65520 KB Output is correct
16 Correct 150 ms 65644 KB Output is correct
17 Correct 118 ms 66572 KB Output is correct
18 Correct 111 ms 66616 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 64764 KB Output is correct
2 Correct 163 ms 64776 KB Output is correct
3 Correct 616 ms 69828 KB Output is correct
4 Correct 150 ms 66088 KB Output is correct
5 Correct 189 ms 65848 KB Output is correct
6 Correct 154 ms 65860 KB Output is correct
7 Correct 188 ms 65928 KB Output is correct
8 Correct 159 ms 65916 KB Output is correct
9 Correct 135 ms 66320 KB Output is correct
10 Correct 204 ms 66372 KB Output is correct
11 Correct 281 ms 66632 KB Output is correct
12 Correct 394 ms 66736 KB Output is correct
13 Correct 668 ms 66884 KB Output is correct
14 Correct 788 ms 70388 KB Output is correct
15 Correct 314 ms 66372 KB Output is correct
16 Correct 351 ms 66540 KB Output is correct
17 Correct 195 ms 67396 KB Output is correct
18 Correct 295 ms 67380 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 356624 KB Output is correct
2 Correct 1034 ms 356600 KB Output is correct
3 Correct 2481 ms 371780 KB Output is correct
4 Correct 971 ms 363560 KB Output is correct
5 Correct 808 ms 361384 KB Output is correct
6 Correct 809 ms 361240 KB Output is correct
7 Correct 778 ms 361284 KB Output is correct
8 Correct 743 ms 361280 KB Output is correct
9 Correct 783 ms 361980 KB Output is correct
10 Correct 906 ms 360340 KB Output is correct
11 Correct 1010 ms 361064 KB Output is correct
12 Correct 1390 ms 361856 KB Output is correct
13 Correct 2234 ms 364220 KB Output is correct
14 Correct 2421 ms 376656 KB Output is correct
15 Correct 1340 ms 364784 KB Output is correct
16 Correct 1359 ms 364636 KB Output is correct
17 Correct 853 ms 364548 KB Output is correct
18 Correct 966 ms 364484 KB Output is correct