oj.uz

Submission #424115

# Submission time Handle Problem Language Result Execution time Memory
424115 2021-06-11T16:55:21 Z ocarima Teams (IOI15_teams) C++14
0 / 100
 751 ms 106224 KB 
#include "teams.h"
#include<bits/stdc++.h>

using namespace std;

#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define repa(i, a, b) for(int i = (a); i >= (b); --i)

#define MAX_N 500002

vector<int> st[1 << 20];
int offset, maxN;

void init(int N, int A[], int B[]) {
    maxN = N;
    offset = 1;
    while (offset < N) offset <<= 1;

    rep(i, 0, N - 1) st[offset + B[i] - 1].emplace_back(A[i]);
    rep(i, 1, N) if (st[i].size()) sort(st[i].begin(), st[i].end());

    repa(i, offset - 1, 1) merge(st[i * 2].begin(), st[i * 2].end(), st[i * 2 + 1].begin(), st[i * 2 + 1].end(), back_inserter(st[i]));
}

int cuenta(int nodo, int s, int e, int up, int down, int r){
    if (s > up || e < down) return 0;
    if (s >= down && e <= up){
        int ini, fin, mitad, cnt;
        ini = 0;
        fin = st[nodo].size() - 1;
        cnt = 0;
        while (ini <= fin){
            mitad = (ini + fin) / 2;
            if (st[nodo][mitad] <= r){
                cnt = mitad + 1;
                ini = mitad + 1;
            }
            else fin = mitad - 1;
        }
        return cnt;
    }

    int mitad = (s + e) / 2;
    return cuenta(nodo * 2, s, mitad, up, down, r) + cuenta(nodo * 2 + 1, mitad + 1, e, up, down, r);
}

int can(int M, int K[]) {

    sort(K, K + M);

    int acarreo, total;

    acarreo = 0;
    rep(i, 0, M - 1){
        total = cuenta(1, 1, offset, maxN, K[i], K[i]);

        total -= acarreo;
        if (total < K[i]){
            return 0;
        }

        if (i < M - 1 && K[i] == K[i + 1]) acarreo += K[i];
        else if (i < M - 1){
            total = cuenta(1, 1, offset, K[i + 1] - 1, K[i], K[i]);
            acarreo = acarreo + K[i] - total;
            if (acarreo < 0) acarreo = 0;
        }
    }

	return 1;
}

Compilation message

teams.cpp: In function 'int cuenta(int, int, int, int, int, int)':
teams.cpp:34:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |         fin = st[nodo].size() - 1;
      |               ~~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24908 KB Output is correct
2 Correct 15 ms 24916 KB Output is correct
3 Correct 14 ms 24916 KB Output is correct
4 Correct 14 ms 24916 KB Output is correct
5 Incorrect 14 ms 24908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 38772 KB Output is correct
2 Correct 61 ms 38684 KB Output is correct
3 Correct 66 ms 38736 KB Output is correct
4 Correct 63 ms 39240 KB Output is correct
5 Correct 31 ms 34984 KB Output is correct
6 Correct 31 ms 34948 KB Output is correct
7 Incorrect 31 ms 35000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 39240 KB Output is correct
2 Correct 80 ms 39340 KB Output is correct
3 Incorrect 199 ms 42568 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 95780 KB Output is correct
2 Correct 385 ms 100636 KB Output is correct
3 Incorrect 751 ms 106224 KB Output isn't correct
4 Halted 0 ms 0 KB -