Submission #64921

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
64921	2018-08-06 06:17:33	leejseo	조화행렬 (KOI18_matrix)	C++98	100 / 100	549 ms	74876 KiB

matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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