# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
65549 |
2018-08-08T01:01:21 Z |
red1108 |
None (KOI18_matrix) |
C++17 |
|
4000 ms |
46780 KB |
#include <bits/stdc++.h>
using namespace std;
struct in{
int x, y,z;
}input[200010];
int n, k,si=1,top=0;
set<pair<int,int> > seg[530000];
pair<int,int> er[200010];
int getmax(int cur, int l, int r, int s, int e, int zz)
{
if(l>r||r<s||e<l) return 0;
if(s<=l&&r<=e)
{
auto it=upper_bound(seg[cur].begin(),seg[cur].end(),pair<int,int>{zz,1000000});
if(it==seg[cur].begin()) return 0;
it--;
return -(*it).second;
}
return max(getmax(cur*2,l,(l+r)/2,s,e,zz),getmax(cur*2+1,(l+r)/2+1,r,s,e,zz));
}
void gang(int pos, int curz, int put)
{
pos=pos+si-1;
while(pos)
{
auto it=lower_bound(seg[pos].begin(),seg[pos].end(),pair<int,int>{curz,-put});
if(it!=seg[pos].begin())
{
auto tmp=it;
it--;
if(-(*it).second>=put) break;
it=tmp;
}
top=0;
while(it!=seg[pos].end()&&-(*it).second<put)
{
er[++top]={(*it).first,(*it).second};
it++;
}
for(int j=1;j<=top;j++)seg[pos].erase(er[j]);
seg[pos].insert({curz,-put});
pos/=2;
}
}
int main()
{
int i,ans=0;
scanf("%d %d",&k,&n);
for(i=1;i<=n;i++) scanf("%d", &input[i].x);
for(i=1;i<=n;i++) scanf("%d", &input[i].y);
if(k==3) for(i=1;i<=n;i++) scanf("%d", &input[i].z);
sort(input+1,input+n+1,[&](in a, in b){return a.y<b.y;});
for(i=1;i<=n;i++) input[i].y=i;
if(k==3) {
sort(input+1,input+n+1,[&](in a, in b){return a.z<b.z;});
for(i=1;i<=n;i++) input[i].z=i;
}
sort(input+1,input+n+1,[&](in a, in b){return a.x<b.x;});
for(i=1;i<=n;i++) input[i].x=i;
while(si<n) si*=2;
for(i=1;i<=n;i++)
{
int t=getmax(1,1,si,1,input[i].y,input[i].z);
gang(input[i].y,input[i].z,t+1);
ans=max(ans,t+1);
}
printf("%d",ans);
}
Compilation message
matrix.cpp: In function 'int main()':
matrix.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&k,&n);
~~~~~^~~~~~~~~~~~~~~
matrix.cpp:49:28: 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", &input[i].x);
~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:50:28: 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", &input[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:51:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if(k==3) for(i=1;i<=n;i++) scanf("%d", &input[i].z);
~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
26232 KB |
Output is correct |
2 |
Correct |
41 ms |
26472 KB |
Output is correct |
3 |
Correct |
42 ms |
26472 KB |
Output is correct |
4 |
Correct |
39 ms |
26472 KB |
Output is correct |
5 |
Correct |
48 ms |
26472 KB |
Output is correct |
6 |
Correct |
43 ms |
26472 KB |
Output is correct |
7 |
Correct |
38 ms |
26472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1297 ms |
28932 KB |
Output is correct |
2 |
Correct |
3651 ms |
30088 KB |
Output is correct |
3 |
Correct |
242 ms |
30088 KB |
Output is correct |
4 |
Correct |
201 ms |
30088 KB |
Output is correct |
5 |
Correct |
526 ms |
30088 KB |
Output is correct |
6 |
Execution timed out |
4027 ms |
30652 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
26232 KB |
Output is correct |
2 |
Correct |
41 ms |
26472 KB |
Output is correct |
3 |
Correct |
42 ms |
26472 KB |
Output is correct |
4 |
Correct |
39 ms |
26472 KB |
Output is correct |
5 |
Correct |
48 ms |
26472 KB |
Output is correct |
6 |
Correct |
43 ms |
26472 KB |
Output is correct |
7 |
Correct |
38 ms |
26472 KB |
Output is correct |
8 |
Correct |
764 ms |
46672 KB |
Output is correct |
9 |
Correct |
610 ms |
46780 KB |
Output is correct |
10 |
Correct |
393 ms |
46780 KB |
Output is correct |
11 |
Correct |
354 ms |
46780 KB |
Output is correct |
12 |
Correct |
501 ms |
46780 KB |
Output is correct |
13 |
Correct |
545 ms |
46780 KB |
Output is correct |
14 |
Correct |
468 ms |
46780 KB |
Output is correct |
15 |
Correct |
274 ms |
46780 KB |
Output is correct |
16 |
Correct |
522 ms |
46780 KB |
Output is correct |
17 |
Correct |
458 ms |
46780 KB |
Output is correct |
18 |
Correct |
420 ms |
46780 KB |
Output is correct |
19 |
Correct |
407 ms |
46780 KB |
Output is correct |
20 |
Correct |
892 ms |
46780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1297 ms |
28932 KB |
Output is correct |
2 |
Correct |
3651 ms |
30088 KB |
Output is correct |
3 |
Correct |
242 ms |
30088 KB |
Output is correct |
4 |
Correct |
201 ms |
30088 KB |
Output is correct |
5 |
Correct |
526 ms |
30088 KB |
Output is correct |
6 |
Execution timed out |
4027 ms |
30652 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |