| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 47253 |
2018-04-29T18:02:57 Z |
aquablitz11 |
Teams (IOI15_teams) |
C++14 |
|
2552 ms |
158388 KB |
// headers
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// types
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using dbl = double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using piipi = pair<pii, int>;
using pipii = pair<int, pii>;
using plpii = pair<ll, pii>;
using ppii = pair<pii, pii>;
// loops
#define forx(i, x, y) for (int i = (x); i <= (y); ++i)
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define for1(i, n) for (int i = 1; i <= (n); ++i)
#define rofx(i, x, y) for (int i = x; i >= y; --i)
#define rofn(i, n) for (int i = n-1; i >= 0; --i)
#define rof1(i, n) for (int i = n; i >= 1; --i)
#define fora(x, v) for (auto x : v)
// define shortcuts
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define X first
#define Y second
#define MP make_pair
#define MT make_tuple
// functions
template<class T> inline bool hasbit(T x, int i) { return x&(1<<i); }
template<class T> inline T togbit(T x, int i) { return x|(1<<i); }
template<class T> inline T setbit(T x, int i) { return x|(1<<i); }
template<class T> inline T rembit(T x, int i) { return x&~(1<<i); }
template<class T> inline bool setmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool setmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> int compress(vector<T> &v) { sort(all(v)); v.resize(unique(all(v))-v.begin()); return v.size(); }
// read functions
int read_int() { int x; scanf("%d", &x); return x; }
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
dbl read_dbl() { dbl x; scanf("%lf", &x); return x; }
void _R(int &x) { x = read_int(); }
void _R(ll &x) { x = read_ll(); }
void _R(dbl &x) { x = read_dbl(); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
// print functions
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%" PRId64, x); }
void _W(const ull &x) { printf("%" PRIu64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
// pseudo-random number generator
template<class T, T x1, T x2, T x3, int y1, int y2, int y3>
struct PRNG {
using S = typename make_signed<T>::type;
T s;
PRNG(T _s = 0) : s(_s) {}
T next() {
T z = (s += x1);
z = (z ^ (z >> y1)) * x2;
z = (z ^ (z >> y2)) * x3;
return z ^ (z >> y3);
}
T next(T n) { return next() % n; }
S next(S l, S r) { return l + next(r - l + 1); }
T operator()() { return next(); }
T operator()(T n) { return next(n); }
S operator()(S l, S r) { return next(l, r); }
static T gen(T s) { return PRNG(s)(); }
template<class U>
void shuffle(U first, U last) {
size_t n = last - first;
for (size_t i = 0; i < n; i++) swap(first[i], first[next(i + 1)]);
}
};
PRNG<uint32_t, 0x9E3779B1, 0x85EBCA6B, 0xC2B2AE35, 16, 13, 16> r32;
PRNG<uint64_t, 0x9E3779B97F4A7C15, 0xBF58476D1CE4E5B9, 0x94D049BB133111EB, 30, 27, 31> r64;
// program
#include "teams.h"
// took two hours to come up with this solution
const int MAXN = 1<<19;
int n;
pii val[MAXN];
vector<int> seg[MAXN<<1];
int _lazy[MAXN<<1], _cntu[MAXN<<1], timl[MAXN<<1], timu[MAXN<<1], tick;
inline int &lazy(int i) {
if (timl[i] != tick) {
timl[i] = tick;
_lazy[i] = 0;
}
return _lazy[i];
}
inline int &cntu(int i) {
if (timu[i] != tick) {
timu[i] = tick;
_cntu[i] = 0;
}
return _cntu[i];
}
inline vector<int> merge(vector<int> &a, vector<int> &b)
{
vector<int> ans;
ans.reserve(a.size() + b.size());
int i = 0, j = 0;
while (i != a.size() || j != b.size()) {
if (j == b.size() || (i != a.size() && a[i] < b[j]))
ans.pb(a[i++]);
else
ans.pb(b[j++]);
}
return ans;
}
void build(int p=1, int b=0, int e=n-1)
{
if (b == e) {
seg[p].pb(val[b].S);
return;
}
int m = (b+e)/2;
build(p<<1, b, m);
build(p<<1|1, m+1, e);
seg[p] = merge(seg[p<<1], seg[p<<1|1]);
}
inline void push(int p=1, int b=0, int e=n-1)
{
if (!lazy(p)) return;
cntu(p) = upper_bound(all(seg[p]), lazy(p)) - seg[p].begin();
if (b != e) {
lazy(p<<1) = lazy(p);
lazy(p<<1|1) = lazy(p);
}
lazy(p) = 0;
}
// pair (all <= A, used)
pii query(int l, int r, int A, int p=1, int b=0, int e=n-1)
{
push(p, b, e);
if (b > r || e < l)
return pii(0, 0);
if (b >= l && e <= r) {
int c = upper_bound(all(seg[p]), A) - seg[p].begin();
return pii(c, cntu(p));
}
int m = (b+e)/2;
pii ql = query(l, r, A, p<<1, b, m);
pii qr = query(l, r, A, p<<1|1, m+1, e);
return pii(ql.F+qr.F, ql.S+qr.S);
}
int bsearch(int x, int A, int p=1, int b=0, int e=n-1)
{
push(p, b, e);
if (b == e)
return b;
int m = (b+e)/2;
push(p<<1, b, m);
push(p<<1|1, m+1, e);
int c = (int)(upper_bound(all(seg[p<<1]), A) - seg[p<<1].begin()) - cntu(p<<1);
if (c >= x)
return bsearch(x, A, p<<1, b, m);
else
return bsearch(x-c, A, p<<1|1, m+1, e);
}
void update(int l, int r, int A, int p=1, int b=0, int e=n-1)
{
push(p, b, e);
if (b > r || e < l)
return;
if (b >= l && e <= r) {
lazy(p) = A;
push(p, b, e);
return;
}
int m = (b+e)/2;
update(l, r, A, p<<1, b, m);
update(l, r, A, p<<1|1, m+1, e);
cntu(p) = cntu(p<<1) + cntu(p<<1|1);
}
void print_tree(int p=1, int b=0, int e=n-1)
{
if (b != e) {
int m = (b+e)/2;
print_tree(p<<1, b, m);
print_tree(p<<1|1, m+1, e);
}
W("node", p, "range", b, e, "has", seg[p]);
}
// =======================
void init(int N, int A[], int B[]) {
n = N;
forn(i, n) val[i] = pii(B[i], A[i]);
sort(val, val+n);
build();
//print_tree();
}
int can(int M, int K[]) {
++tick;
sort(K, K+M);
forn(i, M) {
int k = K[i];
// get start point
int st = lower_bound(val, val+n, pii(k, 0))-val;
if (st == n)
return 0;
// determine existence of end point
pii q = query(st, n-1, k);
if (q.F-q.S < k)
return 0;
// find lowest end point
/*int b = st;
int e = n-1;
while (b < e) {
int m = (b+e)/2;
pii q = query(st, m, k);
if (q.F-q.S >= k)
e = m;
else
b = m+1;
}*/
q = query(0, st-1, k);
int x = q.F-q.S;
int e = bsearch(k+x, k);
if (e < st)
return 0;
// set everything A <= k to used
update(st, e, k);
}
return 1;
}
Compilation message
teams.cpp: In function 'll read_ll()':
teams.cpp:49:42: warning: format '%ld' expects argument of type 'long int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
~~^
teams.cpp: In function 'ull read_ull()':
teams.cpp:50:45: warning: format '%lu' expects argument of type 'long unsigned int*', but argument 2 has type 'ull* {aka long long unsigned int*}' [-Wformat=]
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
~~^
teams.cpp: In function 'void _W(const ll&)':
teams.cpp:60:44: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
void _W(const ll &x) { printf("%" PRId64, x); }
~^
teams.cpp: In function 'void _W(const ull&)':
teams.cpp:61:45: warning: format '%lu' expects argument of type 'long unsigned int', but argument 2 has type 'ull {aka long long unsigned int}' [-Wformat=]
void _W(const ull &x) { printf("%" PRIu64, x); }
~^
teams.cpp: In function 'std::vector<int> merge(std::vector<int>&, std::vector<int>&)':
teams.cpp:127:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i != a.size() || j != b.size()) {
~~^~~~~~~~~~~
teams.cpp:127:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i != a.size() || j != b.size()) {
~~^~~~~~~~~~~
teams.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j == b.size() || (i != a.size() && a[i] < b[j]))
~~^~~~~~~~~~~
teams.cpp:128:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j == b.size() || (i != a.size() && a[i] < b[j]))
~~^~~~~~~~~~~
teams.cpp: In function 'void push(int, int, int)':
teams.cpp:151:49: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
cntu(p) = upper_bound(all(seg[p]), lazy(p)) - seg[p].begin();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp: In function 'pii query(int, int, int, int, int, int)':
teams.cpp:166:45: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
int c = upper_bound(all(seg[p]), A) - seg[p].begin();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:233:52: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
int st = lower_bound(val, val+n, pii(k, 0))-val;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
teams.cpp: In function 'int read_int()':
teams.cpp:48:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int read_int() { int x; scanf("%d", &x); return x; }
~~~~~^~~~~~~~~~
teams.cpp: In function 'll read_ll()':
teams.cpp:49:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
~~~~~^~~~~~~~~~~~~~~~
teams.cpp: In function 'ull read_ull()':
teams.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
~~~~~^~~~~~~~~~~~~~~~
teams.cpp: In function 'dbl read_dbl()':
teams.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
dbl read_dbl() { dbl x; scanf("%lf", &x); return x; }
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24996 KB |
Output is correct |
| 2 |
Correct |
23 ms |
25064 KB |
Output is correct |
| 3 |
Correct |
25 ms |
25132 KB |
Output is correct |
| 4 |
Correct |
29 ms |
25184 KB |
Output is correct |
| 5 |
Correct |
24 ms |
25184 KB |
Output is correct |
| 6 |
Correct |
24 ms |
25224 KB |
Output is correct |
| 7 |
Correct |
29 ms |
25224 KB |
Output is correct |
| 8 |
Correct |
23 ms |
25240 KB |
Output is correct |
| 9 |
Correct |
23 ms |
25240 KB |
Output is correct |
| 10 |
Correct |
23 ms |
25240 KB |
Output is correct |
| 11 |
Correct |
26 ms |
25292 KB |
Output is correct |
| 12 |
Correct |
33 ms |
25292 KB |
Output is correct |
| 13 |
Correct |
24 ms |
25292 KB |
Output is correct |
| 14 |
Correct |
24 ms |
25292 KB |
Output is correct |
| 15 |
Correct |
23 ms |
25292 KB |
Output is correct |
| 16 |
Correct |
24 ms |
25292 KB |
Output is correct |
| 17 |
Correct |
24 ms |
25292 KB |
Output is correct |
| 18 |
Correct |
23 ms |
25292 KB |
Output is correct |
| 19 |
Correct |
30 ms |
25292 KB |
Output is correct |
| 20 |
Correct |
30 ms |
25292 KB |
Output is correct |
| 21 |
Correct |
23 ms |
25292 KB |
Output is correct |
| 22 |
Correct |
23 ms |
25292 KB |
Output is correct |
| 23 |
Correct |
23 ms |
25292 KB |
Output is correct |
| 24 |
Correct |
24 ms |
25292 KB |
Output is correct |
| 25 |
Correct |
23 ms |
25292 KB |
Output is correct |
| 26 |
Correct |
24 ms |
25292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
38708 KB |
Output is correct |
| 2 |
Correct |
84 ms |
38708 KB |
Output is correct |
| 3 |
Correct |
86 ms |
38708 KB |
Output is correct |
| 4 |
Correct |
96 ms |
38892 KB |
Output is correct |
| 5 |
Correct |
80 ms |
42172 KB |
Output is correct |
| 6 |
Correct |
80 ms |
42172 KB |
Output is correct |
| 7 |
Correct |
81 ms |
42172 KB |
Output is correct |
| 8 |
Correct |
76 ms |
42172 KB |
Output is correct |
| 9 |
Correct |
167 ms |
42620 KB |
Output is correct |
| 10 |
Correct |
99 ms |
42620 KB |
Output is correct |
| 11 |
Correct |
78 ms |
42620 KB |
Output is correct |
| 12 |
Correct |
73 ms |
42620 KB |
Output is correct |
| 13 |
Correct |
76 ms |
42620 KB |
Output is correct |
| 14 |
Correct |
77 ms |
42620 KB |
Output is correct |
| 15 |
Correct |
83 ms |
42620 KB |
Output is correct |
| 16 |
Correct |
80 ms |
42620 KB |
Output is correct |
| 17 |
Correct |
76 ms |
42620 KB |
Output is correct |
| 18 |
Correct |
76 ms |
42620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
42620 KB |
Output is correct |
| 2 |
Correct |
92 ms |
42620 KB |
Output is correct |
| 3 |
Correct |
573 ms |
45792 KB |
Output is correct |
| 4 |
Correct |
90 ms |
45792 KB |
Output is correct |
| 5 |
Correct |
413 ms |
45792 KB |
Output is correct |
| 6 |
Correct |
379 ms |
45792 KB |
Output is correct |
| 7 |
Correct |
81 ms |
45792 KB |
Output is correct |
| 8 |
Correct |
328 ms |
45792 KB |
Output is correct |
| 9 |
Correct |
163 ms |
45792 KB |
Output is correct |
| 10 |
Correct |
208 ms |
45792 KB |
Output is correct |
| 11 |
Correct |
255 ms |
45792 KB |
Output is correct |
| 12 |
Correct |
439 ms |
45792 KB |
Output is correct |
| 13 |
Correct |
655 ms |
45792 KB |
Output is correct |
| 14 |
Correct |
732 ms |
45792 KB |
Output is correct |
| 15 |
Correct |
287 ms |
45792 KB |
Output is correct |
| 16 |
Correct |
271 ms |
45792 KB |
Output is correct |
| 17 |
Correct |
313 ms |
45792 KB |
Output is correct |
| 18 |
Correct |
287 ms |
45792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
97024 KB |
Output is correct |
| 2 |
Correct |
430 ms |
97948 KB |
Output is correct |
| 3 |
Correct |
2109 ms |
118932 KB |
Output is correct |
| 4 |
Correct |
409 ms |
118932 KB |
Output is correct |
| 5 |
Correct |
1654 ms |
118932 KB |
Output is correct |
| 6 |
Correct |
1274 ms |
118932 KB |
Output is correct |
| 7 |
Correct |
350 ms |
118932 KB |
Output is correct |
| 8 |
Correct |
1104 ms |
118932 KB |
Output is correct |
| 9 |
Correct |
878 ms |
118932 KB |
Output is correct |
| 10 |
Correct |
735 ms |
120744 KB |
Output is correct |
| 11 |
Correct |
1155 ms |
124512 KB |
Output is correct |
| 12 |
Correct |
1452 ms |
128904 KB |
Output is correct |
| 13 |
Correct |
2237 ms |
135272 KB |
Output is correct |
| 14 |
Correct |
2552 ms |
145876 KB |
Output is correct |
| 15 |
Correct |
994 ms |
145876 KB |
Output is correct |
| 16 |
Correct |
1016 ms |
145876 KB |
Output is correct |
| 17 |
Correct |
1079 ms |
151664 KB |
Output is correct |
| 18 |
Correct |
957 ms |
158388 KB |
Output is correct |
