| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 64921 | 2018-08-06T06:17:33 Z | leejseo | 조화행렬 (KOI18_matrix) | C++ | 549 ms | 74876 KB |
#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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 27 ms | 10488 KB | Output is correct |
| 2 | Correct | 20 ms | 10788 KB | Output is correct |
| 3 | Correct | 21 ms | 11060 KB | Output is correct |
| 4 | Correct | 19 ms | 11324 KB | Output is correct |
| 5 | Correct | 30 ms | 11520 KB | Output is correct |
| 6 | Correct | 20 ms | 11800 KB | Output is correct |
| 7 | Correct | 21 ms | 11920 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 12020 KB | Output is correct |
| 2 | Correct | 31 ms | 12540 KB | Output is correct |
| 3 | Correct | 32 ms | 12540 KB | Output is correct |
| 4 | Correct | 35 ms | 12664 KB | Output is correct |
| 5 | Correct | 24 ms | 13084 KB | Output is correct |
| 6 | Correct | 26 ms | 13716 KB | Output is correct |
| 7 | Correct | 22 ms | 13716 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 27 ms | 10488 KB | Output is correct |
| 2 | Correct | 20 ms | 10788 KB | Output is correct |
| 3 | Correct | 21 ms | 11060 KB | Output is correct |
| 4 | Correct | 19 ms | 11324 KB | Output is correct |
| 5 | Correct | 30 ms | 11520 KB | Output is correct |
| 6 | Correct | 20 ms | 11800 KB | Output is correct |
| 7 | Correct | 21 ms | 11920 KB | Output is correct |
| 8 | Correct | 398 ms | 30440 KB | Output is correct |
| 9 | Correct | 343 ms | 33692 KB | Output is correct |
| 10 | Correct | 210 ms | 33740 KB | Output is correct |
| 11 | Correct | 302 ms | 33744 KB | Output is correct |
| 12 | Correct | 215 ms | 33756 KB | Output is correct |
| 13 | Correct | 158 ms | 33756 KB | Output is correct |
| 14 | Correct | 222 ms | 33756 KB | Output is correct |
| 15 | Correct | 309 ms | 33756 KB | Output is correct |
| 16 | Correct | 229 ms | 34776 KB | Output is correct |
| 17 | Correct | 183 ms | 38732 KB | Output is correct |
| 18 | Correct | 179 ms | 42468 KB | Output is correct |
| 19 | Correct | 224 ms | 46332 KB | Output is correct |
| 20 | Correct | 548 ms | 50284 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 28 ms | 12020 KB | Output is correct |
| 2 | Correct | 31 ms | 12540 KB | Output is correct |
| 3 | Correct | 32 ms | 12540 KB | Output is correct |
| 4 | Correct | 35 ms | 12664 KB | Output is correct |
| 5 | Correct | 24 ms | 13084 KB | Output is correct |
| 6 | Correct | 26 ms | 13716 KB | Output is correct |
| 7 | Correct | 22 ms | 13716 KB | Output is correct |
| 8 | Correct | 260 ms | 50284 KB | Output is correct |
| 9 | Correct | 338 ms | 50284 KB | Output is correct |
| 10 | Correct | 200 ms | 50284 KB | Output is correct |
| 11 | Correct | 213 ms | 51712 KB | Output is correct |
| 12 | Correct | 279 ms | 51712 KB | Output is correct |
| 13 | Correct | 274 ms | 59284 KB | Output is correct |
| 14 | Correct | 346 ms | 61876 KB | Output is correct |
| 15 | Correct | 300 ms | 70512 KB | Output is correct |
| 16 | Correct | 258 ms | 70588 KB | Output is correct |
| 17 | Correct | 336 ms | 70588 KB | Output is correct |
| 18 | Correct | 329 ms | 70588 KB | Output is correct |
| 19 | Correct | 202 ms | 70588 KB | Output is correct |
| 20 | Correct | 298 ms | 70588 KB | Output is correct |
| 21 | Correct | 195 ms | 70588 KB | Output is correct |
| 22 | Correct | 321 ms | 70588 KB | Output is correct |
| 23 | Correct | 292 ms | 70588 KB | Output is correct |
| 24 | Correct | 195 ms | 70588 KB | Output is correct |
| 25 | Correct | 311 ms | 70588 KB | Output is correct |
| 26 | Correct | 439 ms | 73800 KB | Output is correct |
| 27 | Correct | 222 ms | 73800 KB | Output is correct |
| 28 | Correct | 236 ms | 73800 KB | Output is correct |
| 29 | Correct | 361 ms | 73800 KB | Output is correct |
| 30 | Correct | 270 ms | 73800 KB | Output is correct |
| 31 | Correct | 549 ms | 74876 KB | Output is correct |
| 32 | Correct | 320 ms | 74876 KB | Output is correct |