This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "teams.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
#define lsb(x) (x & -x)
struct AIB {
int faking = 1;
vector<int> nrm;
vector<int> tree;
AIB(): faking(1) { nrm.clear(); tree.clear(); }
void upd(int p, int x) {
if(faking) { nrm.emplace_back(p); return; }
p = distance(begin(nrm), upper_bound(all(nrm), p));
while(p > 0) tree[p] += x, p -= lsb(p);
return;
}
int query(int p) {
int sum = 0;
assert(!faking);
p = distance(begin(nrm), lower_bound(all(nrm), p)) + 1;
while(p < sz(tree)) sum += tree[p], p += lsb(p);
return sum;
}
void donefaking() {
faking = 0;
sort(all(nrm));
nrm.erase(unique(all(nrm)), end(nrm));
tree.resize(sz(nrm) + 2, 0);
}
};
struct AIB2D {
vector<AIB> tree;
void init(int n) {
tree.assign(n + 2, AIB());
}
int query(int l, int r) {
int sum = 0;
while(l > 0) {
sum += tree[l].query(r);
l -= lsb(l);
}
return sum;
}
void upd(int l, int r, int x) {
while(l < sz(tree))
tree[l].upd(r, x),
l += lsb(l);
return;
}
void donefaking() { for(auto &x : tree) x.donefaking(); }
};
AIB2D sums;
vector<pii> pula;
int Query(int x) {
int a = sums.query(x, x);
return a;
}
int Query(int x, int not_y) {
return sums.query(x, x) - sums.query(x, not_y);
}
void init(int n, int A[], int B[]) {
sums.init(n + 1);
for(int i = 0; i < n; i++)
pula.emplace_back(A[i], B[i]),
sums.upd(A[i], B[i], 1);
sums.donefaking();
for(int i = 0; i < n; i++)
sums.upd(A[i], B[i], 1);
return;
}
int can(int M, int K[]) {
int sofar = 0;
sort(K, K + M);
vector<int> dp(M, 0);
for(int i = 0; i < M; i++) {
for(int j = i - 1, a = 0; a <= 4 && j >= 0; a++, j--) // trebuie sa incerc
dp[i] = min(dp[i], dp[j] + Query(K[j], K[i]) - K[j]);
if(dp[i] + Query(K[i]) - K[i] < 0) return 0;
}
return 1;
}
Compilation message (stderr)
teams.cpp: In member function 'void AIB::upd(int, int)':
teams.cpp:23:19: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
23 | p = distance(begin(nrm), upper_bound(all(nrm), p));
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'int AIB::query(int)':
teams.cpp:30:58: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
30 | p = distance(begin(nrm), lower_bound(all(nrm), p)) + 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:91:8: warning: unused variable 'sofar' [-Wunused-variable]
91 | int sofar = 0;
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |