oj.uz

Submission #127175

# Submission time Handle Problem Language Result Execution time Memory
127175 2019-07-09T03:42:26 Z arnold518 None (KOI18_matrix) C++14
23 / 100
 4000 ms 17444 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, dp[MAXN+10], ans;
struct tup
{
    int a, b, c;
    bool operator < (const tup& p) { return a<p.a; }
};
tup A[MAXN+10];

struct BIT
{
    vector<int> tree;
    BIT() : tree(N+10, 0) {}
    void update(int i, int val) { for(; i<=N; i+=(i&-i)) tree[i]=max(tree[i], val); }
    int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }
};

void solve(int s, int e)
{
    int i, j;
    if(s==e)
    {
        dp[s]=max(dp[s], 1);
        return;
    }

    int mid=s+e>>1;
    solve(s, mid);

    vector<tup> L, R;
    for(i=s; i<=mid; i++) L.push_back({A[i].b, A[i].c, dp[i]});
    for(i=mid+1; i<=e; i++) R.push_back({A[i].b, A[i].c, i});
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());

    BIT bit;

    int pt=0;
    for(i=0; i<R.size(); i++)
    {
        while(pt<L.size() && L[pt].a<R[i].a) bit.update(L[pt].b, L[pt].c), pt++;
        dp[R[i].c]=max(dp[R[i].c], bit.query(R[i].b)+1);
    }

    solve(mid+1, e);
}

int main()
{
    int i, j;

    scanf("%d%d", &M, &N);

    vector<int> Vb, Vc;
    for(i=1; i<=N; i++) scanf("%d", &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), Vc.push_back(A[i].c);
    else for(i=1; i<=N; i++) A[i].c=A[i].a, Vc.push_back(A[i].c);

    sort(Vb.begin(), Vb.end());
    sort(Vc.begin(), Vc.end());

    for(i=1; i<=N; i++) A[i].b=lower_bound(Vb.begin(), Vb.end(), A[i].b)-Vb.begin()+1;
    for(i=1; i<=N; i++) A[i].c=lower_bound(Vc.begin(), Vc.end(), A[i].c)-Vc.begin()+1;

    sort(A+1, A+N+1);

    solve(1, N);
    for(i=1; i<=N; i++) ans=max(ans, dp[i]);
    printf("%d", ans);
}

Compilation message

matrix.cpp: In function 'void solve(int, int)':
matrix.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=s+e>>1;
             ~^~
matrix.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<R.size(); i++)
              ~^~~~~~~~~
matrix.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pt<L.size() && L[pt].a<R[i].a) bit.update(L[pt].b, L[pt].c), pt++;
               ~~^~~~~~~~~
matrix.cpp:28:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
matrix.cpp: In function 'int main()':
matrix.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
matrix.cpp:60: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:63:30: 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);
                         ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:64: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:65:54: 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), Vc.push_back(A[i].c);
                                  ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1748 KB Output is correct
2 Correct 100 ms 1612 KB Output is correct
3 Correct 100 ms 1688 KB Output is correct
4 Correct 102 ms 1656 KB Output is correct
5 Correct 101 ms 1688 KB Output is correct
6 Correct 96 ms 1688 KB Output is correct
7 Correct 99 ms 1712 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1724 KB Output is correct
2 Correct 101 ms 1776 KB Output is correct
3 Correct 104 ms 1716 KB Output is correct
4 Correct 104 ms 1688 KB Output is correct
5 Correct 103 ms 1716 KB Output is correct
6 Correct 98 ms 1688 KB Output is correct
7 Correct 103 ms 1816 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1748 KB Output is correct
2 Correct 100 ms 1612 KB Output is correct
3 Correct 100 ms 1688 KB Output is correct
4 Correct 102 ms 1656 KB Output is correct
5 Correct 101 ms 1688 KB Output is correct
6 Correct 96 ms 1688 KB Output is correct
7 Correct 99 ms 1712 KB Output is correct
8 Execution timed out 4011 ms 17444 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1724 KB Output is correct
2 Correct 101 ms 1776 KB Output is correct
3 Correct 104 ms 1716 KB Output is correct
4 Correct 104 ms 1688 KB Output is correct
5 Correct 103 ms 1716 KB Output is correct
6 Correct 98 ms 1688 KB Output is correct
7 Correct 103 ms 1816 KB Output is correct
8 Execution timed out 4014 ms 17244 KB Time limit exceeded
9 Halted 0 ms 0 KB -