# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
99627 |
2019-03-05T21:54:49 Z |
andremfq |
Teams (IOI15_teams) |
C++17 |
|
1808 ms |
141568 KB |
//codigo Yan
#include <bits/stdc++.h>
#define ff first
#define ss second
#define MAX 500010
#define OO 1000000010
using namespace std;
typedef pair<int,int> pii;
class PersistentSegTree
{
public:
void build(int i)
{
e.push_back(e[i]);
d.push_back(d[i]);
s.push_back(s[i]);
}
int update(int id, int ini, int fim, int i)
{
int novo = ++node_cur;
build(id);
if(ini == fim)
{
s[novo]++;
return novo;
}
int m = (ini + fim)/2;
if(i <= m)
{
int aux = update(e[novo] , ini , m , i);
e[novo] = aux;
}
else
{
int aux = update(d[novo] , m + 1 , fim , i);
d[novo] = aux;
}
s[novo] = s[e[novo]] + s[d[novo]];
return novo;
}
int query(int id , int ini , int fim , int i, int j)
{
if(id == 0 || ini > j || fim < i) return 0;
if(i <= ini && fim <= j) return s[id];
int m = (ini + fim)/2;
return query(e[id] , ini , m , i , j) + query(d[id] , m + 1 , fim , i , j);
}
int bs(int r1, int r2 , int ini , int fim , int v)
{
if(ini == fim) return ini;
int b = s[e[r2]] - s[e[r1]];
int m = (ini + fim)/2;
if(b >= v) return bs(e[r1] , e[r2] , ini , m , v);
return bs(d[r1] , d[r2] , m + 1 , fim , v - b);
}
PersistentSegTree()
{
e.push_back(0); e.push_back(0);
d.push_back(0); d.push_back(0);
s.push_back(0); s.push_back(0);
}
private:
vector<int> e, d;
vector<int> s;
int node_cur = 1;
} SEG;
int n;
int root[MAX];
pii points[MAX];
int rectangle_sum(int x1, int x2, int y1, int y2)
{
int s1 = SEG.query(root[x2] , 0 , n , y1 , y2);
int s2 = SEG.query(root[x1 - 1] , 0 , n , y1 , y2);
return s1 - s2;
}
class bars
{
public:
int l, r, h;
int corner;
bars(int ll, int rr, int hh, int cc)
{
l = ll;
r = rr;
h = hh;
corner = cc;
}
};
class pilha
{
public:
bool push(int i, int h)
{
bars k(i , i , h , 0);
while(h >= p.back().h)
{
k.l = p.back().l;
p.pop_back();
}
int s = i;
while(!p.empty())
{
int ll = p.back().l;
int lr = p.back().r;
int lh = p.back().h;
int lc = p.back().corner;
int rs = rectangle_sum(lr + 1 , k.r , k.h + 1 , lh);
if(rs > s)
{
int nh = SEG.bs(root[lr] , root[k.r] , 0 , n , s + rectangle_sum(lr + 1 , k.r , 0 , k.h));
int tot = rectangle_sum(lr + 1 , k.r , k.h + 1 , nh);
k.h = nh;
k.l = lr + 1;
k.corner = tot - s;
p.push_back(k);
return true;
}
k.l = ll;
k.h = lh;
p.pop_back();
if(rs <= s && s <= rs + lc)
{
k.corner = lc - (s - rs);
p.push_back(k);
return true;
}
s -= rs + lc;
}
return false;
}
void clear()
{
p.clear();
bars k(-OO , 0 , OO , 0);
p.push_back(k);
}
pilha()
{
bars k(-OO , 0 , OO , 0);
p.push_back(k);
}
private:
vector<bars> p;
};
void init(int N, int A[], int B[])
{
n = N;
for(int g = 0 ; g < n ; g++) points[g].ff = A[g];
for(int g = 0 ; g < n ; g++) points[g].ss = B[g];
sort(points , points + n);
int i = 0;
root[0] = 1;
for(int g = 1 ; g <= n ; g++)
{
root[g] = root[g - 1];
while(i < n && points[i].ff == g)
{
int aux = SEG.update(root[g] , 0 , n , points[i].ss);
root[g] = aux;
i++;
}
}
}
int can(int M, int K[])
{
sort(K , K + M);
bool error = true;
pilha s;
for(int g = 0 ; g < M && error ; g++) error = error && s.push(K[g] , K[g] - 1);
return (error) ? 1 : 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
356 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
356 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
3 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
23668 KB |
Output is correct |
2 |
Correct |
93 ms |
23600 KB |
Output is correct |
3 |
Correct |
112 ms |
23552 KB |
Output is correct |
4 |
Correct |
97 ms |
24036 KB |
Output is correct |
5 |
Correct |
59 ms |
23628 KB |
Output is correct |
6 |
Correct |
61 ms |
23936 KB |
Output is correct |
7 |
Correct |
60 ms |
23728 KB |
Output is correct |
8 |
Correct |
60 ms |
23828 KB |
Output is correct |
9 |
Correct |
60 ms |
22960 KB |
Output is correct |
10 |
Correct |
58 ms |
24236 KB |
Output is correct |
11 |
Correct |
56 ms |
24100 KB |
Output is correct |
12 |
Correct |
56 ms |
24112 KB |
Output is correct |
13 |
Correct |
64 ms |
24108 KB |
Output is correct |
14 |
Correct |
62 ms |
23340 KB |
Output is correct |
15 |
Correct |
82 ms |
23824 KB |
Output is correct |
16 |
Correct |
82 ms |
23772 KB |
Output is correct |
17 |
Correct |
67 ms |
24100 KB |
Output is correct |
18 |
Correct |
65 ms |
24108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
23740 KB |
Output is correct |
2 |
Correct |
89 ms |
23844 KB |
Output is correct |
3 |
Correct |
318 ms |
26644 KB |
Output is correct |
4 |
Correct |
104 ms |
23836 KB |
Output is correct |
5 |
Correct |
93 ms |
24084 KB |
Output is correct |
6 |
Correct |
89 ms |
24084 KB |
Output is correct |
7 |
Correct |
66 ms |
24092 KB |
Output is correct |
8 |
Correct |
94 ms |
24064 KB |
Output is correct |
9 |
Correct |
66 ms |
22964 KB |
Output is correct |
10 |
Correct |
82 ms |
24400 KB |
Output is correct |
11 |
Correct |
93 ms |
24344 KB |
Output is correct |
12 |
Correct |
110 ms |
24468 KB |
Output is correct |
13 |
Correct |
265 ms |
24348 KB |
Output is correct |
14 |
Correct |
486 ms |
25532 KB |
Output is correct |
15 |
Correct |
135 ms |
24220 KB |
Output is correct |
16 |
Correct |
150 ms |
24220 KB |
Output is correct |
17 |
Correct |
115 ms |
24476 KB |
Output is correct |
18 |
Correct |
104 ms |
24468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
790 ms |
141248 KB |
Output is correct |
2 |
Correct |
784 ms |
141408 KB |
Output is correct |
3 |
Correct |
1609 ms |
141308 KB |
Output is correct |
4 |
Correct |
790 ms |
141232 KB |
Output is correct |
5 |
Correct |
524 ms |
140172 KB |
Output is correct |
6 |
Correct |
481 ms |
140284 KB |
Output is correct |
7 |
Correct |
404 ms |
140184 KB |
Output is correct |
8 |
Correct |
468 ms |
140316 KB |
Output is correct |
9 |
Correct |
412 ms |
140200 KB |
Output is correct |
10 |
Correct |
415 ms |
140368 KB |
Output is correct |
11 |
Correct |
435 ms |
140284 KB |
Output is correct |
12 |
Correct |
534 ms |
140220 KB |
Output is correct |
13 |
Correct |
1073 ms |
140436 KB |
Output is correct |
14 |
Correct |
1808 ms |
141172 KB |
Output is correct |
15 |
Correct |
760 ms |
141420 KB |
Output is correct |
16 |
Correct |
729 ms |
141568 KB |
Output is correct |
17 |
Correct |
493 ms |
140668 KB |
Output is correct |
18 |
Correct |
497 ms |
140604 KB |
Output is correct |