oj.uz

Submission #791554

# Submission time Handle Problem Language Result Execution time Memory
791554 2023-07-24T07:22:02 Z 반딧불(#10046) Sličnost (COI23_slicnost) C++17
50 / 100
 540 ms 359812 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Update{
    int t, l, r, v;
    Update(){}
    Update(int t, int l, int r, int v): t(t), l(l), r(r), v(v){}

    bool operator<(const Update &nxt)const{
        return t<nxt.t;
    }
};

struct PST{
    struct Node{
        Node *lc, *rc;
        int val, maxSum, maxCnt; /// �� ������ ���� +��, �� ���������� �ִ�

        Node(){
            lc = rc = nullptr;
            val = maxSum = 0, maxCnt = 1;
        }
        Node(Node *lc, Node *rc, int val, int maxSum, int maxCnt):
            lc(lc), rc(rc), val(val), maxSum(maxSum), maxCnt(maxCnt){}

        void init(int l, int r){
            if(l==r) return;
            int m = (l+r)>>1;
            lc = new Node();
            lc->init(l, m);
            rc = new Node();
            rc->init(m+1, r);
            maxCnt = lc->maxCnt + rc->maxCnt;
        }

        Node* update(int l, int r, int s, int e, int v){
            if(s<=l && r<=e){
                Node* tmp = new Node(lc, rc, val, maxSum, maxCnt);
                tmp->val += v;
                if(l==r) tmp->maxSum = tmp->val;
                else{
                    tmp->maxSum = tmp->val + max(tmp->lc->maxSum, tmp->rc->maxSum);
                    tmp->maxCnt = (tmp->lc->maxSum >= tmp->rc->maxSum ? tmp->lc->maxCnt : 0) +
                                  (tmp->rc->maxSum >= tmp->lc->maxSum ? tmp->rc->maxCnt : 0);
                }
                return tmp;
            }
            int m = (l+r)>>1;
            Node* tmp = new Node(lc, rc, val, maxSum, maxCnt);
            if(s<=m) tmp->lc = lc->update(l, m, s, e, v);
            if(m<e)  tmp->rc = rc->update(m+1, r, s, e, v);
            tmp->maxSum = tmp->val + max(tmp->lc->maxSum, tmp->rc->maxSum);
            tmp->maxCnt = (tmp->lc->maxSum >= tmp->rc->maxSum ? tmp->lc->maxCnt : 0) +
                          (tmp->rc->maxSum >= tmp->lc->maxSum ? tmp->rc->maxCnt : 0);
            return tmp;
        }
    } *root[200002];
    int L;
    map<int, ll> mp;

    inline void mpAdd(int x, ll v){
        mp[x] += v;
    }

    inline void mpErase(int x, ll v){
        mp[x] -= v;
        if(!mp[x]) mp.erase(x);
    }

    void init(int _L, vector<Update> &vec){
        L = _L;
        root[0] = new Node();
        root[0]->init(1, L);

        int pnt = 0;
        for(int t=1; t<=L*2; t++){
            root[t] = root[t-1];
            while(pnt < (int)vec.size() && vec[pnt].t == t){
                root[t] = root[t]->update(1, L, vec[pnt].l, vec[pnt].r, vec[pnt].v);
//                printf("Root %d: add %d %d %d\n", vec[pnt].t, vec[pnt].l, vec[pnt].r, vec[pnt].v);
                pnt++;
            }
            if(t%2) mpAdd(root[t]->maxSum, root[t]->maxCnt);
        }
    }

    void update(int t, vector<Update> &vec){
        if(t%2) mpErase(root[t]->maxSum, root[t]->maxCnt);
        for(Update p: vec){
            root[t] = root[t]->update(1, L, p.l, p.r, p.v);
        }
        if(t%2) mpAdd(root[t]->maxSum, root[t]->maxCnt);
    }

    void printAns(){
        printf("%d %lld\n", mp.rbegin()->first, mp.rbegin()->second);
    }
} tree;

int n, k, q;
int a[100002], idx[100002];
int in[100002], out[100002];

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        idx[x] = i;
    }

    /// �ʱ� ���� ���� �����
    vector<Update> updateVec;
    for(int i=1; i<=n; i++){
        in[i] = max(1, i-k+1);
        out[i] = min(i, n-k+1);
    }
    for(int i=1; i<=n; i++){
        updateVec.push_back(Update(in[i]*2-1, in[idx[a[i]]], out[idx[a[i]]], 1));
        updateVec.push_back(Update(out[i]*2, in[idx[a[i]]], out[idx[a[i]]], -1));
    }
    sort(updateVec.begin(), updateVec.end());
    tree.init(n-k+1, updateVec);
    tree.printAns();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:109:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     for(int i=1; i<=n; i++) scanf("%d", &a[i]);
      |                             ~~~~~^~~~~~~~~~~~~
Main.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 7 ms 7248 KB Output is correct
17 Correct 8 ms 7692 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 9 ms 8148 KB Output is correct
20 Correct 13 ms 11984 KB Output is correct
21 Correct 12 ms 12624 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 13 ms 11516 KB Output is correct
24 Correct 11 ms 11856 KB Output is correct
25 Correct 11 ms 9792 KB Output is correct
26 Correct 12 ms 11120 KB Output is correct
27 Correct 14 ms 12748 KB Output is correct
28 Correct 9 ms 8784 KB Output is correct
29 Correct 9 ms 6500 KB Output is correct
30 Correct 2 ms 1872 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 7 ms 7248 KB Output is correct
17 Correct 8 ms 7692 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 9 ms 8148 KB Output is correct
20 Correct 13 ms 11984 KB Output is correct
21 Correct 12 ms 12624 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 13 ms 11516 KB Output is correct
24 Correct 11 ms 11856 KB Output is correct
25 Correct 11 ms 9792 KB Output is correct
26 Correct 12 ms 11120 KB Output is correct
27 Correct 14 ms 12748 KB Output is correct
28 Correct 9 ms 8784 KB Output is correct
29 Correct 9 ms 6500 KB Output is correct
30 Correct 2 ms 1872 KB Output is correct
31 Correct 204 ms 178760 KB Output is correct
32 Correct 217 ms 189336 KB Output is correct
33 Correct 27 ms 15068 KB Output is correct
34 Correct 272 ms 217840 KB Output is correct
35 Correct 434 ms 318364 KB Output is correct
36 Correct 328 ms 359812 KB Output is correct
37 Correct 41 ms 32264 KB Output is correct
38 Correct 440 ms 303684 KB Output is correct
39 Correct 307 ms 316716 KB Output is correct
40 Correct 352 ms 264424 KB Output is correct
41 Correct 426 ms 302016 KB Output is correct
42 Correct 540 ms 358540 KB Output is correct
43 Correct 312 ms 234508 KB Output is correct
44 Correct 235 ms 172228 KB Output is correct
45 Correct 55 ms 40580 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Incorrect 0 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 7 ms 7248 KB Output is correct
17 Correct 8 ms 7692 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 9 ms 8148 KB Output is correct
20 Correct 13 ms 11984 KB Output is correct
21 Correct 12 ms 12624 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 13 ms 11516 KB Output is correct
24 Correct 11 ms 11856 KB Output is correct
25 Correct 11 ms 9792 KB Output is correct
26 Correct 12 ms 11120 KB Output is correct
27 Correct 14 ms 12748 KB Output is correct
28 Correct 9 ms 8784 KB Output is correct
29 Correct 9 ms 6500 KB Output is correct
30 Correct 2 ms 1872 KB Output is correct
31 Incorrect 0 ms 340 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 7 ms 7248 KB Output is correct
17 Correct 8 ms 7692 KB Output is correct
18 Correct 3 ms 972 KB Output is correct
19 Correct 9 ms 8148 KB Output is correct
20 Correct 13 ms 11984 KB Output is correct
21 Correct 12 ms 12624 KB Output is correct
22 Correct 3 ms 1488 KB Output is correct
23 Correct 13 ms 11516 KB Output is correct
24 Correct 11 ms 11856 KB Output is correct
25 Correct 11 ms 9792 KB Output is correct
26 Correct 12 ms 11120 KB Output is correct
27 Correct 14 ms 12748 KB Output is correct
28 Correct 9 ms 8784 KB Output is correct
29 Correct 9 ms 6500 KB Output is correct
30 Correct 2 ms 1872 KB Output is correct
31 Correct 204 ms 178760 KB Output is correct
32 Correct 217 ms 189336 KB Output is correct
33 Correct 27 ms 15068 KB Output is correct
34 Correct 272 ms 217840 KB Output is correct
35 Correct 434 ms 318364 KB Output is correct
36 Correct 328 ms 359812 KB Output is correct
37 Correct 41 ms 32264 KB Output is correct
38 Correct 440 ms 303684 KB Output is correct
39 Correct 307 ms 316716 KB Output is correct
40 Correct 352 ms 264424 KB Output is correct
41 Correct 426 ms 302016 KB Output is correct
42 Correct 540 ms 358540 KB Output is correct
43 Correct 312 ms 234508 KB Output is correct
44 Correct 235 ms 172228 KB Output is correct
45 Correct 55 ms 40580 KB Output is correct
46 Incorrect 0 ms 340 KB Output isn't correct
47 Halted 0 ms 0 KB -