oj.uz

Submission #64863

# Submission time Handle Problem Language Result Execution time Memory
64863 2018-08-06T00:15:37 Z gs18115 None (KOI18_matrix) C++14
23 / 100
 48 ms 21536 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int INF=1e9;
struct matrix
{
    int x,y,z;
    matrix()
    {
        x=y=z=0;
    }
}mat[123456];
bool cmp1(matrix a,matrix b)
{
    return a.x<b.x;
}
bool cmp2(matrix a,matrix b)
{
    return a.y<b.y;
}
bool cmp3(matrix a,matrix b)
{
    return a.z<b.z;
}
set<pair<int,int> >S[123456];
bool fp(int x,int y,int k)
{
    set<pair<int,int> >::iterator it=lower_bound(S[k].begin(),S[k].end(),make_pair(x,-INF));
    if(it==S[k].begin())
        return false;
    it--;
    if(it->second>y)
        return false;
    return true;
}
void ap(int x,int y,int k)
{
    if(fp(x,y,k))
        return;
    while(true)
    {
        set<pair<int,int> >::iterator it=lower_bound(S[k].begin(),S[k].end(),make_pair(x,INF));
        if(it->second>y)
            S[k].erase(it);
        else
            break;
    }
    S[k].insert(make_pair(x,y));
    return;
}
int M,N,i;
int maxi,s,e,mid;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>M>>N;
    for(i=0;i<N;i++)
        cin>>mat[i].x;
    for(i=0;i<N;i++)
        cin>>mat[i].y;
    for(i=0;i<N;i++)
    {
        if(M==2)
            mat[i].z=mat[i].y;
        else
            cin>>mat[i].z;
    }
    sort(mat,mat+N,cmp2);
    for(i=0;i<N;i++)
        mat[i].y=i+1;
    sort(mat,mat+N,cmp3);
    for(i=0;i<N;i++)
        mat[i].z=i+1;
    sort(mat,mat+N,cmp1);
    ap(0,0,0);
    maxi=1;
    for(i=0;i<N;i++)
    {
        s=0;e=maxi;
        while(s<e)
        {
            mid=s+e+1>>1;
            if(fp(mat[i].y,mat[i].z,mid))
                s=mid;
            else
                e=mid-1;
        }
        if(s+2>maxi)
            maxi=s+2;
        ap(mat[i].y,mat[i].z,s+1);
    }
    cout<<maxi-1;
    return 0;
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:86:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             mid=s+e+1>>1;
                 ~~~^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7800 KB Output is correct
2 Correct 19 ms 8236 KB Output is correct
3 Correct 18 ms 8248 KB Output is correct
4 Correct 18 ms 8736 KB Output is correct
5 Correct 19 ms 8736 KB Output is correct
6 Correct 20 ms 9312 KB Output is correct
7 Correct 21 ms 9380 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9704 KB Output is correct
2 Correct 22 ms 10032 KB Output is correct
3 Correct 32 ms 10224 KB Output is correct
4 Correct 45 ms 10516 KB Output is correct
5 Correct 36 ms 10808 KB Output is correct
6 Correct 19 ms 11360 KB Output is correct
7 Correct 41 ms 11404 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7800 KB Output is correct
2 Correct 19 ms 8236 KB Output is correct
3 Correct 18 ms 8248 KB Output is correct
4 Correct 18 ms 8736 KB Output is correct
5 Correct 19 ms 8736 KB Output is correct
6 Correct 20 ms 9312 KB Output is correct
7 Correct 21 ms 9380 KB Output is correct
8 Runtime error 48 ms 19984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9704 KB Output is correct
2 Correct 22 ms 10032 KB Output is correct
3 Correct 32 ms 10224 KB Output is correct
4 Correct 45 ms 10516 KB Output is correct
5 Correct 36 ms 10808 KB Output is correct
6 Correct 19 ms 11360 KB Output is correct
7 Correct 41 ms 11404 KB Output is correct
8 Runtime error 40 ms 21536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -