oj.uz

Submission #127177

# Submission time Handle Problem Language Result Execution time Memory
127177 2019-07-09T03:46:30 Z arnold518 None (KOI18_matrix) C++14
100 / 100
 658 ms 13424 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
{
    int tree[MAXN+10];
    BIT bit() { memset(tree, 0, sizeof(tree)); }
    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 flush(int i) { for(; i<=N; i+=(i&-i)) tree[i]=0; }
};
BIT bit;

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());

    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);
    }
    for(i=0; i<L.size(); i++) bit.flush(L[i].b);

    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 member function 'BIT BIT::bit()':
matrix.cpp:21:48: warning: no return statement in function returning non-void [-Wreturn-type]
     BIT bit() { memset(tree, 0, sizeof(tree)); }
                                                ^
matrix.cpp: In function 'void solve(int, int)':
matrix.cpp:37: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:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<L.size(); i++) bit.flush(L[i].b);
              ~^~~~~~~~~
matrix.cpp:30:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
matrix.cpp: In function 'int main()':
matrix.cpp:59:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
matrix.cpp:61: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:64: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:65: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:66: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 23 ms 884 KB Output is correct
2 Correct 22 ms 884 KB Output is correct
3 Correct 24 ms 884 KB Output is correct
4 Correct 22 ms 884 KB Output is correct
5 Correct 23 ms 884 KB Output is correct
6 Correct 18 ms 884 KB Output is correct
7 Correct 21 ms 884 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 884 KB Output is correct
2 Correct 23 ms 884 KB Output is correct
3 Correct 25 ms 884 KB Output is correct
4 Correct 25 ms 884 KB Output is correct
5 Correct 24 ms 856 KB Output is correct
6 Correct 20 ms 884 KB Output is correct
7 Correct 25 ms 944 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 884 KB Output is correct
2 Correct 22 ms 884 KB Output is correct
3 Correct 24 ms 884 KB Output is correct
4 Correct 22 ms 884 KB Output is correct
5 Correct 23 ms 884 KB Output is correct
6 Correct 18 ms 884 KB Output is correct
7 Correct 21 ms 884 KB Output is correct
8 Correct 592 ms 10780 KB Output is correct
9 Correct 584 ms 13340 KB Output is correct
10 Correct 528 ms 13080 KB Output is correct
11 Correct 382 ms 13296 KB Output is correct
12 Correct 581 ms 13104 KB Output is correct
13 Correct 432 ms 13316 KB Output is correct
14 Correct 564 ms 13216 KB Output is correct
15 Correct 381 ms 13232 KB Output is correct
16 Correct 424 ms 13088 KB Output is correct
17 Correct 433 ms 13272 KB Output is correct
18 Correct 503 ms 13112 KB Output is correct
19 Correct 550 ms 13208 KB Output is correct
20 Correct 597 ms 13232 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 884 KB Output is correct
2 Correct 23 ms 884 KB Output is correct
3 Correct 25 ms 884 KB Output is correct
4 Correct 25 ms 884 KB Output is correct
5 Correct 24 ms 856 KB Output is correct
6 Correct 20 ms 884 KB Output is correct
7 Correct 25 ms 944 KB Output is correct
8 Correct 588 ms 10676 KB Output is correct
9 Correct 582 ms 13080 KB Output is correct
10 Correct 539 ms 13388 KB Output is correct
11 Correct 457 ms 13272 KB Output is correct
12 Correct 466 ms 13364 KB Output is correct
13 Correct 561 ms 13232 KB Output is correct
14 Correct 618 ms 13240 KB Output is correct
15 Correct 455 ms 13336 KB Output is correct
16 Correct 461 ms 13216 KB Output is correct
17 Correct 572 ms 13208 KB Output is correct
18 Correct 657 ms 13080 KB Output is correct
19 Correct 623 ms 13212 KB Output is correct
20 Correct 610 ms 13424 KB Output is correct
21 Correct 457 ms 13088 KB Output is correct
22 Correct 658 ms 13272 KB Output is correct
23 Correct 576 ms 13336 KB Output is correct
24 Correct 622 ms 13084 KB Output is correct
25 Correct 628 ms 13136 KB Output is correct
26 Correct 634 ms 13220 KB Output is correct
27 Correct 464 ms 13212 KB Output is correct
28 Correct 463 ms 13316 KB Output is correct
29 Correct 576 ms 13392 KB Output is correct
30 Correct 572 ms 13212 KB Output is correct
31 Correct 634 ms 13168 KB Output is correct
32 Correct 584 ms 13220 KB Output is correct