# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
127158 |
2019-07-09T01:51:23 Z |
arnold518 |
None (KOI18_matrix) |
C++14 |
|
3849 ms |
601368 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
int M, N, ans;
struct Data
{
int a, b, c;
bool operator < (const Data& p) { return c<p.c; }
};
Data A[MAXN+10];
struct Node1
{
Node1() : val(0), lc(NULL), rc(NULL) {}
int val;
Node1 *lc, *rc;
};
Node1 *tree[MAXN+10];
void update1(Node1 *node, int tl, int tr, int pos, int val)
{
if(tl==tr)
{
node->val=val;
return;
}
int mid=tl+tr>>1;
if(pos<=mid)
{
if(node->lc==NULL) node->lc=new Node1;
update1(node->lc, tl, mid, pos, val);
}
else
{
if(node->rc==NULL) node->rc=new Node1;
update1(node->rc, mid+1, tr, pos, val);
}
node->val=0;
if(node->lc!=NULL) node->val=max(node->val, node->lc->val);
if(node->rc!=NULL) node->val=max(node->val, node->rc->val);
}
int query1(Node1 *node, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return node->val;
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
int ret=0;
if(node->lc!=NULL) ret=max(ret, query1(node->lc, tl, mid, l, r));
if(node->rc!=NULL) ret=max(ret, query1(node->rc, mid+1, tr, l, r));
return ret;
}
void update2(int ypos, int xpos, int val) { for(int i=ypos; i<=N; i+=(i&-i)) update1(tree[i], 1, N, xpos, val); }
int query2(int ypos, int xpos) { int ret=0; for(int i=ypos; i>0; i-=(i&-i)) ret=max(ret, query1(tree[i], 1, N, 1, xpos)); return ret; }
int main()
{
int i, j;
scanf("%d%d", &M, &N);
for(i=1; i<=N; i++) tree[i]=new Node1();
vector<int> Va, Vb;
for(i=1; i<=N; i++) scanf("%d", &A[i].a), Va.push_back(A[i].a);
for(i=1; i<=N; i++) scanf("%d", &A[i].b), Vb.push_back(A[i].b);
if(M==3) for(i=1; i<=N; i++) scanf("%d", &A[i].c);
else for(i=1; i<=N; i++) A[i].c=A[i].a;
sort(Va.begin(), Va.end());
sort(Vb.begin(), Vb.end());
for(i=1; i<=N; i++) A[i].a=lower_bound(Va.begin(), Va.end(), A[i].a)-Va.begin()+1;
for(i=1; i<=N; i++) A[i].b=lower_bound(Vb.begin(), Vb.end(), A[i].b)-Vb.begin()+1;
sort(A+1, A+N+1);
for(i=1; i<=N; i++)
{
int now=query2(A[i].a, A[i].b)+1;
ans=max(ans, now);
update2(A[i].a, A[i].b, now);
}
printf("%d", ans);
}
Compilation message
matrix.cpp: In function 'void update1(Node1*, int, int, int, int)':
matrix.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
matrix.cpp: In function 'int query1(Node1*, int, int, int, int)':
matrix.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
matrix.cpp: In function 'int main()':
matrix.cpp:65:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
matrix.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &M, &N);
~~~~~^~~~~~~~~~~~~~~~
matrix.cpp:71:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%d", &A[i].a), Va.push_back(A[i].a);
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:72:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%d", &A[i].b), Vb.push_back(A[i].b);
~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:73:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if(M==3) for(i=1; i<=N; i++) scanf("%d", &A[i].c);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
18680 KB |
Output is correct |
2 |
Correct |
49 ms |
13048 KB |
Output is correct |
3 |
Correct |
56 ms |
15480 KB |
Output is correct |
4 |
Correct |
42 ms |
11104 KB |
Output is correct |
5 |
Correct |
62 ms |
17912 KB |
Output is correct |
6 |
Correct |
36 ms |
9208 KB |
Output is correct |
7 |
Correct |
38 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
11228 KB |
Output is correct |
2 |
Correct |
40 ms |
9976 KB |
Output is correct |
3 |
Correct |
61 ms |
15608 KB |
Output is correct |
4 |
Correct |
76 ms |
18808 KB |
Output is correct |
5 |
Correct |
52 ms |
13176 KB |
Output is correct |
6 |
Correct |
37 ms |
9336 KB |
Output is correct |
7 |
Correct |
71 ms |
18068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
18680 KB |
Output is correct |
2 |
Correct |
49 ms |
13048 KB |
Output is correct |
3 |
Correct |
56 ms |
15480 KB |
Output is correct |
4 |
Correct |
42 ms |
11104 KB |
Output is correct |
5 |
Correct |
62 ms |
17912 KB |
Output is correct |
6 |
Correct |
36 ms |
9208 KB |
Output is correct |
7 |
Correct |
38 ms |
9848 KB |
Output is correct |
8 |
Correct |
2390 ms |
579928 KB |
Output is correct |
9 |
Correct |
2131 ms |
507780 KB |
Output is correct |
10 |
Correct |
1150 ms |
269060 KB |
Output is correct |
11 |
Correct |
1012 ms |
230504 KB |
Output is correct |
12 |
Correct |
1782 ms |
430188 KB |
Output is correct |
13 |
Correct |
1006 ms |
230672 KB |
Output is correct |
14 |
Correct |
1596 ms |
362472 KB |
Output is correct |
15 |
Correct |
1012 ms |
230508 KB |
Output is correct |
16 |
Correct |
1008 ms |
230572 KB |
Output is correct |
17 |
Correct |
1028 ms |
230560 KB |
Output is correct |
18 |
Correct |
1098 ms |
244912 KB |
Output is correct |
19 |
Correct |
1293 ms |
308396 KB |
Output is correct |
20 |
Correct |
2567 ms |
599360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
11228 KB |
Output is correct |
2 |
Correct |
40 ms |
9976 KB |
Output is correct |
3 |
Correct |
61 ms |
15608 KB |
Output is correct |
4 |
Correct |
76 ms |
18808 KB |
Output is correct |
5 |
Correct |
52 ms |
13176 KB |
Output is correct |
6 |
Correct |
37 ms |
9336 KB |
Output is correct |
7 |
Correct |
71 ms |
18068 KB |
Output is correct |
8 |
Correct |
1359 ms |
304576 KB |
Output is correct |
9 |
Correct |
2100 ms |
426744 KB |
Output is correct |
10 |
Correct |
1107 ms |
246884 KB |
Output is correct |
11 |
Correct |
1042 ms |
232520 KB |
Output is correct |
12 |
Correct |
2363 ms |
232356 KB |
Output is correct |
13 |
Correct |
1192 ms |
271080 KB |
Output is correct |
14 |
Correct |
2161 ms |
432060 KB |
Output is correct |
15 |
Correct |
1035 ms |
232424 KB |
Output is correct |
16 |
Correct |
1051 ms |
232420 KB |
Output is correct |
17 |
Correct |
2033 ms |
433256 KB |
Output is correct |
18 |
Correct |
3849 ms |
601264 KB |
Output is correct |
19 |
Correct |
2047 ms |
601164 KB |
Output is correct |
20 |
Correct |
1630 ms |
364352 KB |
Output is correct |
21 |
Correct |
1039 ms |
232548 KB |
Output is correct |
22 |
Correct |
3735 ms |
581660 KB |
Output is correct |
23 |
Correct |
1904 ms |
432996 KB |
Output is correct |
24 |
Correct |
2035 ms |
601368 KB |
Output is correct |
25 |
Correct |
3008 ms |
509804 KB |
Output is correct |
26 |
Correct |
2484 ms |
601056 KB |
Output is correct |
27 |
Correct |
2363 ms |
232576 KB |
Output is correct |
28 |
Correct |
1030 ms |
232420 KB |
Output is correct |
29 |
Correct |
2024 ms |
432532 KB |
Output is correct |
30 |
Correct |
1985 ms |
432608 KB |
Output is correct |
31 |
Correct |
2473 ms |
601308 KB |
Output is correct |
32 |
Correct |
1952 ms |
433124 KB |
Output is correct |