oj.uz

Submission #127157

# Submission time Handle Problem Language Result Execution time Memory
127157 2019-07-09T01:42:10 Z arnold518 None (KOI18_matrix) C++14
23 / 100
 4000 ms 786436 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2e5;

int M, N, ans;
struct Data
{
    int a, b, c;
    bool operator < (const Data& p) { return a<p.a; }
};
Data A[MAXN+10];

struct Node1
{
    Node1() : val(0), lc(NULL), rc(NULL) {}
    int val;
    Node1 *lc, *rc;
};

struct Node2
{
    Node2() : val(0), lc(NULL), rc(NULL) {}
    Node1 *val;
    Node2 *lc, *rc;
};
Node2 *root=new Node2;

void update1(Node1 *node, int tl, int tr, int pos, int val)
{
    if(tl==tr)
    {
        node->val=val;
        return;
    }
    int mid=tl+tr>>1;
    if(pos<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1;
        update1(node->lc, tl, mid, pos, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1;
        update1(node->rc, mid+1, tr, pos, val);
    }
    node->val=0;
    if(node->lc!=NULL) node->val=max(node->val, node->lc->val);
    if(node->rc!=NULL) node->val=max(node->val, node->rc->val);
}

int query1(Node1 *node, int tl, int tr, int l, int r)
{
    if(l<=tl && tr<=r) return node->val;
    if(r<tl || tr<l) return 0;
    int mid=tl+tr>>1;
    int ret=0;
    if(node->lc!=NULL) ret=max(ret, query1(node->lc, tl, mid, l, r));
    if(node->rc!=NULL) ret=max(ret, query1(node->rc, mid+1, tr, l, r));
    return ret;
}

void update2(Node2 *node, int tl, int tr, int ypos, int xpos, int val)
{
    if(node->val==NULL) node->val=new Node1;
    if(tl==tr)
    {
        update1(node->val, 1, N, xpos, val);
        return;
    }
    int mid=tl+tr>>1;
    if(ypos<=mid)
    {
        if(node->lc==NULL) node->lc=new Node2;
        update2(node->lc, tl, mid, ypos, xpos, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node2;
        update2(node->rc, mid+1, tr, ypos, xpos, val);
    }
    int t=0;
    if(node->lc!=NULL) t=max(t, query1(node->lc->val, 1, N, xpos, xpos));
    if(node->rc!=NULL) t=max(t, query1(node->rc->val, 1, N, xpos, xpos));
    update1(node->val, 1, N, xpos, t);
}

int query2(Node2 *node, int tl, int tr, int yl, int yr, int xl, int xr)
{
    if(yl<=tl && tr<=yr)
    {
        if(node->val!=NULL) return query1(node->val, 1, N, xl, xr);
        else return 0;
    }
    if(tr<yl || yr<tl) return 0;
    int mid=tl+tr>>1;
    int ret=0;
    if(node->lc!=NULL) ret=max(ret, query2(node->lc, tl, mid, yl, yr, xl, xr));
    if(node->rc!=NULL) ret=max(ret, query2(node->rc, mid+1, tr, yl, yr, xl, xr));
    return ret;
}

int main()
{
    int i, j;

    scanf("%d%d", &M, &N);

    vector<int> Vb, Vc;
    for(i=1; i<=N; i++) scanf("%d", &A[i].a);
    for(i=1; i<=N; i++) scanf("%d", &A[i].b), Vb.push_back(A[i].b);
    if(M==3) for(i=1; i<=N; i++) scanf("%d", &A[i].c), Vc.push_back(A[i].c);

    sort(A+1, A+N+1);

    if(M==2) for(i=1; i<=N; i++) A[i].c=i, Vc.push_back(A[i].c);

    sort(Vb.begin(), Vb.end());
    sort(Vc.begin(), Vc.end());

    for(i=1; i<=N; i++) A[i].b=lower_bound(Vb.begin(), Vb.end(), A[i].b)-Vb.begin()+1;
    for(i=1; i<=N; i++) A[i].c=lower_bound(Vc.begin(), Vc.end(), A[i].c)-Vc.begin()+1;

    for(i=1; i<=N; i++)
    {
        int now=query2(root, 1, N, 1, A[i].b, 1, A[i].c)+1;
        ans=max(ans, now);
        update2(root, 1, N, A[i].b, A[i].c, now);
    }
    printf("%d", ans);
}

Compilation message

matrix.cpp: In function 'void update1(Node1*, int, int, int, int)':
matrix.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
matrix.cpp: In function 'int query1(Node1*, int, int, int, int)':
matrix.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
matrix.cpp: In function 'void update2(Node2*, int, int, int, int, int)':
matrix.cpp:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
matrix.cpp: In function 'int query2(Node2*, int, int, int, int, int, int)':
matrix.cpp:100:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
matrix.cpp: In function 'int main()':
matrix.cpp:109:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
matrix.cpp:111: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:114:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &A[i].a);
                         ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:115:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &A[i].b), Vb.push_back(A[i].b);
                         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:116:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     if(M==3) for(i=1; i<=N; i++) scanf("%d", &A[i].c), Vc.push_back(A[i].c);
                                  ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 37240 KB Output is correct
2 Correct 108 ms 25848 KB Output is correct
3 Correct 121 ms 30968 KB Output is correct
4 Correct 94 ms 22128 KB Output is correct
5 Correct 138 ms 35832 KB Output is correct
6 Correct 78 ms 17400 KB Output is correct
7 Correct 86 ms 19704 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22136 KB Output is correct
2 Correct 93 ms 19704 KB Output is correct
3 Correct 149 ms 31096 KB Output is correct
4 Correct 192 ms 37240 KB Output is correct
5 Correct 123 ms 26048 KB Output is correct
6 Correct 80 ms 17528 KB Output is correct
7 Correct 203 ms 36016 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 37240 KB Output is correct
2 Correct 108 ms 25848 KB Output is correct
3 Correct 121 ms 30968 KB Output is correct
4 Correct 94 ms 22128 KB Output is correct
5 Correct 138 ms 35832 KB Output is correct
6 Correct 78 ms 17400 KB Output is correct
7 Correct 86 ms 19704 KB Output is correct
8 Runtime error 3778 ms 786436 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22136 KB Output is correct
2 Correct 93 ms 19704 KB Output is correct
3 Correct 149 ms 31096 KB Output is correct
4 Correct 192 ms 37240 KB Output is correct
5 Correct 123 ms 26048 KB Output is correct
6 Correct 80 ms 17528 KB Output is correct
7 Correct 203 ms 36016 KB Output is correct
8 Correct 3446 ms 624472 KB Output is correct
9 Execution timed out 4089 ms 723472 KB Time limit exceeded
10 Halted 0 ms 0 KB -