oj.uz

Submission #443769

# Submission time Handle Problem Language Result Execution time Memory
443769 2021-07-12T04:18:28 Z xiaowuc1 None (KOI18_matrix) C++17
29 / 100
 188 ms 8848 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

void twosolve(int n) {
  vector<array<int, 2>> v(n);
  for(int i = 0; i < 2; i++) {
    vector<int> vals;
    vector<int> sorted;
    for(int a = 0; a < n; a++) {
      int x;
      cin >> x;
      vals.pb(x);
      sorted.pb(x);
    }
    sort(all(sorted));
    for(auto& x: vals) x = lb(all(sorted), x) - sorted.begin();
    for(int a = 0; a < n; a++) v[a][i] = vals[a];
  }
  sort(all(v));
  vector<int> dp(n+1);
  int ret = 0;
  for(int i = 0; i < n; i++) {
    int lhs = 0;
    int rhs = ret;
    while(lhs < rhs) {
      int mid = (lhs+rhs+1)/2;
      if(v[i][1] > v[dp[mid]][1]) lhs = mid;
      else rhs = mid-1;
    }
    ret = max(ret, lhs+1);
    dp[++lhs] = i;
  }
  cout << ret << "\n";
}

void solve() {
  int r, c;
  cin >> r >> c;
  if(r == 2) twosolve(c);
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 8 ms 716 KB Output is correct
3 Correct 8 ms 716 KB Output is correct
4 Correct 8 ms 716 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 7 ms 732 KB Output is correct
7 Correct 8 ms 716 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 8 ms 716 KB Output is correct
3 Correct 8 ms 716 KB Output is correct
4 Correct 8 ms 716 KB Output is correct
5 Correct 8 ms 844 KB Output is correct
6 Correct 7 ms 732 KB Output is correct
7 Correct 8 ms 716 KB Output is correct
8 Correct 188 ms 8636 KB Output is correct
9 Correct 180 ms 8612 KB Output is correct
10 Correct 176 ms 8580 KB Output is correct
11 Correct 170 ms 8848 KB Output is correct
12 Correct 178 ms 8744 KB Output is correct
13 Correct 176 ms 8600 KB Output is correct
14 Correct 178 ms 8604 KB Output is correct
15 Correct 167 ms 8704 KB Output is correct
16 Correct 170 ms 8664 KB Output is correct
17 Correct 179 ms 8588 KB Output is correct
18 Correct 173 ms 8576 KB Output is correct
19 Correct 176 ms 8716 KB Output is correct
20 Correct 183 ms 8680 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -