Submission #127177

#	Time	Username	Problem	Language	Result	Execution time	Memory
127177		arnold518	조화행렬 (KOI18_matrix)	C++14	100 / 100	658 ms	13424 KiB

matrix

#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 (stderr)

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 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62