oj.uz

Submission #361622

# Submission time Handle Problem Language Result Execution time Memory
361622 2021-01-30T20:35:40 Z gratus907 None (KOI18_matrix) C++17
38 / 100
 4000 ms 404836 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;
void solve_2();
int m, n;
int arr[3][202020];
set <int> s;
const int MAXR = 606060;
const int MAXC = 606060;

// max-dynamic-2seg
// msg555 impl, some modifications
struct Dynamic2DSeg
{
    struct Node
    {
        Node (int l, int r, int v = 0) : l(l), r(r), v(v), lc(NULL), rc(NULL){}
        int l, r, v;
        Node *lc, *rc;
    };
    struct RowNode
    {
        RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
        Node rowRoot;
        RowNode *lc, *rc;
    };
    RowNode root;
    static void update2(Node *node, int idx, int dt)
    {
        int lo = node -> l;
        int hi = node -> r;
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
        {
            node -> v = dt;
            return;
        }
        Node *& next = idx < mid ? node -> lc : node -> rc;
        if (next == NULL)
            next = new Node(idx, idx + 1, dt);
        else if (next -> l <= idx && idx < next -> r)
            update2(next, idx, dt);
        else
        {
            do {
                (idx < mid ? hi : lo) = mid;
                mid = (lo + hi) / 2;
            } while ((idx < mid) == (next->l < mid));
            Node * nnode = new Node(lo, hi);
            (next->l < mid ? nnode->lc : nnode->rc) = next;
            next = nnode;

            update2(nnode, idx, dt);
        }
        node -> v = max(node->lc?node->lc->v:0, node->rc?node->rc->v:0);
    }
    static void update1(RowNode * node, int lo, int hi, int ridx, int idx, int dt)
    {
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
            update2(&node -> rowRoot, idx, dt);
        else
        {
            RowNode *& nnode = ridx < mid ? node -> lc : node -> rc;
            (ridx < mid ? hi : lo) = mid;
            if (nnode == NULL)
                nnode = new RowNode();
            update1(nnode, lo, hi, ridx, idx, dt);
            dt = max(node->lc ? query2(&node->lc->rowRoot, idx, idx + 1) : 0,
                     node->rc ? query2(&node->rc->rowRoot, idx, idx + 1) : 0);
            update2(&node->rowRoot, idx, dt);
        }
    }
    static int query2(Node *node, int a, int b)
    {
        if (node == NULL || b <= node -> l || node -> r <= a)
            return 0;
        else if (a <= node -> l && node -> r <= b)
            return node -> v;
        return max(query2(node->lc, a, b), query2(node->rc, a, b));
    }
    static int query1(RowNode *node, int lo, int hi, int a1, int b1, int a2, int b2)
    {
        if (node == NULL || b1 <= lo || hi <= a1)
            return 0;
        else if (a1 <= lo && hi <= b1)
            return query2(&node->rowRoot, a2, b2);
        int mid = (lo + hi) / 2;
        return max(query1(node->lc, lo, mid, a1, b1, a2, b2),
                   query1(node->rc, mid, hi, a1, b1, a2, b2));
    }
    void update(int x, int y, int dt)
    {
        update1(&root, 0, MAXR, x, y, dt);
    }
    int query(int x1, int y1, int x2, int y2)
    {
        return query1(&root, 0, MAXR, x1, x2 + 1, y1, y2 + 1);
    }
} DSEG;

void solve_3()
{
    vector <pair<int, pii>> v;
    for (int i = 0; i < n; i++)
        v.push_back({arr[0][i], {arr[1][i], arr[2][i]}});
    sort(all(v));
    vector <int> ans(n, 0);
    for (int i = n-1; i >= 0; i--)
    {
        int cx = v[i].second.first;
        int cy = v[i].second.second;
        ans[i] = DSEG.query(cx+1, cy+1, 1e9+1, 1e9+1) + 1;
        DSEG.update(cx, cy, ans[i]);
    }
    int r = 0;
    for (auto it:ans)
        r = max(it, r);
    cout << r << '\n';
}

vector <int> compress;
int32_t main()
{
    usecppio
    cin >> m >> n;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
            compress.push_back(arr[i][j]);
        }
    }
    sort(all(compress));
    compress.erase(unique(all(compress)), compress.end());
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            arr[i][j] = lower_bound(all(compress), arr[i][j]) - compress.begin();
    if (m == 2)
        solve_2();
    else solve_3();
}


void solve_2()
{
    vector <pii> v;
    for (int i = 0; i < n; i++)
        v.push_back({arr[0][i], arr[1][i]});
    sort(all(v));
    vector <int> vv;
    for (int i = 0; i < n; i++)
        vv.push_back(v[i].second);
    set <int> :: iterator it;
    for (int i = 0; i < n; i++)
    {
        s.insert(vv[i]);
        it = s.upper_bound(vv[i]);
        if (it != s.end())
            s.erase(it);
    }
    cout << s.size() << '\n';
}

Compilation message

matrix.cpp: In constructor 'Dynamic2DSeg::RowNode::RowNode()':
matrix.cpp:32:23: warning: 'Dynamic2DSeg::RowNode::rc' will be initialized after [-Wreorder]
   32 |         RowNode *lc, *rc;
      |                       ^~
matrix.cpp:31:14: warning:   'Dynamic2DSeg::Node Dynamic2DSeg::RowNode::rowRoot' [-Wreorder]
   31 |         Node rowRoot;
      |              ^~~~~~~
matrix.cpp:30:9: warning:   when initialized here [-Wreorder]
   30 |         RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
      |         ^~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 876 KB Output is correct
2 Correct 12 ms 876 KB Output is correct
3 Correct 9 ms 876 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 9 ms 876 KB Output is correct
6 Correct 9 ms 1260 KB Output is correct
7 Correct 9 ms 1004 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 20588 KB Output is correct
2 Correct 70 ms 20588 KB Output is correct
3 Correct 102 ms 20600 KB Output is correct
4 Correct 139 ms 20572 KB Output is correct
5 Correct 85 ms 20588 KB Output is correct
6 Correct 56 ms 20588 KB Output is correct
7 Correct 129 ms 20588 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 876 KB Output is correct
2 Correct 12 ms 876 KB Output is correct
3 Correct 9 ms 876 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 9 ms 876 KB Output is correct
6 Correct 9 ms 1260 KB Output is correct
7 Correct 9 ms 1004 KB Output is correct
8 Correct 208 ms 7524 KB Output is correct
9 Correct 210 ms 7528 KB Output is correct
10 Correct 204 ms 8676 KB Output is correct
11 Correct 183 ms 7528 KB Output is correct
12 Correct 206 ms 7528 KB Output is correct
13 Correct 231 ms 11236 KB Output is correct
14 Correct 206 ms 7676 KB Output is correct
15 Correct 180 ms 7684 KB Output is correct
16 Correct 234 ms 15996 KB Output is correct
17 Correct 230 ms 11108 KB Output is correct
18 Correct 209 ms 10596 KB Output is correct
19 Correct 208 ms 7544 KB Output is correct
20 Correct 207 ms 7524 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 20588 KB Output is correct
2 Correct 70 ms 20588 KB Output is correct
3 Correct 102 ms 20600 KB Output is correct
4 Correct 139 ms 20572 KB Output is correct
5 Correct 85 ms 20588 KB Output is correct
6 Correct 56 ms 20588 KB Output is correct
7 Correct 129 ms 20588 KB Output is correct
8 Correct 1800 ms 399408 KB Output is correct
9 Correct 2259 ms 396668 KB Output is correct
10 Correct 1373 ms 399068 KB Output is correct
11 Correct 1187 ms 399228 KB Output is correct
12 Correct 2612 ms 391244 KB Output is correct
13 Correct 1546 ms 399204 KB Output is correct
14 Correct 3238 ms 398792 KB Output is correct
15 Correct 1261 ms 404784 KB Output is correct
16 Correct 1195 ms 404828 KB Output is correct
17 Correct 2266 ms 404836 KB Output is correct
18 Execution timed out 4078 ms 300028 KB Time limit exceeded
19 Halted 0 ms 0 KB -