Submission #64921

#	Time	Username	Problem	Language	Result	Execution time	Memory
64921		leejseo	조화행렬 (KOI18_matrix)	C++98	100 / 100	549 ms	74876 KiB

matrix

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pii;
const int MAXN = 200001;
 
typedef struct DP{
    // Note that all numbers are different
    // Data structure for 2D LIS Query
    set<pii> S[MAXN+1];
    DP(){}
    void update(int i, pii &p){
        //Amortized O(log N)
        //Each pii is inserted at most once and deleted at most once
        S[i].insert(p);
        set<pii>::iterator it;
        it = S[i].lower_bound(p);
        if (it != S[i].begin()){
            --it;
            if ((*it).second < p.second){
                ++it;
                S[i].erase(it);
                return;
            }
        }
        while(1){
            it = S[i].lower_bound(p);
            ++it;
            if (it == S[i].end()) break;
            if ((*it).second < p.second) break;
            else S[i].erase(it);
        }
    }
 
    bool check(int i, pii&p){
        set<pii>::iterator it;
        it = S[i].lower_bound(p);
        if (it == S[i].begin()) return 0;
        --it;
        return ((*it).second < p.second);
    }
} DP;
 
DP D;
 
vector<pii> L;
 
int solve(){
    int N = L.size();
    int ans = 0;
    for (int i=0; i<N; i++){
        int lo = 0, hi = N-1;
        while (lo < hi){
            int mid = (lo + hi)/2 + 1;
            if (D.check(mid, L[i])) lo = mid;
            else hi = mid-1;
        }
        D.update(lo+1, L[i]);
        ans = max(ans, lo+1);
    }
    return ans;
}
 
typedef pair<int, pii> tri;
vector<tri> V;
 
void init(){
    int M, N;
    scanf("%d%d", &M, &N);
    V.resize(N);
    L.resize(N);
    if (M == 2){
        for (int i=0; i<N; i++) scanf("%d", &V[i].first);
        for (int i=0; i<N; i++) scanf("%d", &V[i].second.first);
        sort(V.begin(), V.end());
        for (int i=0; i<N; i++) L[i].first = V[i].second.first, L[i].second = i;
    }
    else{
        for (int i=0; i<N; i++) scanf("%d", &V[i].first);
        for (int i=0; i<N; i++) scanf("%d", &V[i].second.first);
        for (int i=0; i<N; i++) scanf("%d", &V[i].second.second);
        sort(V.begin(), V.end());
        for (int i=0; i<N; i++) L[i].first = V[i].second.first, L[i].second = V[i].second.second;
    }
}
 
int main(){
    init();
    printf("%d\n", solve());
}

Compilation message (stderr)

matrix.cpp: In function 'void init()':
matrix.cpp:69: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:73:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for (int i=0; i<N; i++) scanf("%d", &V[i].first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:74:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for (int i=0; i<N; i++) scanf("%d", &V[i].second.first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:79:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for (int i=0; i<N; i++) scanf("%d", &V[i].first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:80:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for (int i=0; i<N; i++) scanf("%d", &V[i].second.first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:81:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for (int i=0; i<N; i++) scanf("%d", &V[i].second.second);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62