oj.uz

답안 #973149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973149 2024-05-01T14:35:48 Z yusuf12360 서열 (APIO23_sequence) C++17
20 / 100
 807 ms 58536 KB 
#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct node{
    int mn, mx;
    node(int mini=0, int maxi=0) : mn(mini), mx(maxi) {}
};
int n;
vector<vector<int>> pos;
vector<int> lazy;
vector<node> tr;
void change(int pos, int add) {
    tr[pos].mn+=add;
    tr[pos].mx+=add;
    lazy[pos]+=add;
}
node pull(node L, node R) {
    int MN, MX;
    MN=min(L.mn, R.mn);
    MX=max(L.mx, R.mx);
    return node(MN, MX);
}
void push(int pos) {
    change(2*pos+1, lazy[pos]);
    change(2*pos+2, lazy[pos]);
    lazy[pos]=0;
}
void update(int ll, int rr, int add, int pos=0, int l=0, int r=n-1) {
    if(ll>rr) return;
    if(ll==l && rr==r) {change(pos, add); return;}
    push(pos); int mid=l+r>>1;
    update(ll, min(rr, mid), add, 2*pos+1, l, mid);
    update(max(mid+1, ll), rr, add, 2*pos+2, mid+1, r);
    tr[pos]=pull(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n-1) {
    if(ll>rr) return node(INF, -INF);
    if(ll==l && rr==r) return tr[pos];
    push(pos); int mid=l+r>>1;
    return pull(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
node build(int pos=0, int l=0, int r=n-1) {
    lazy[pos]=0;
    if(l==r) return tr[pos]=node(l+1, r+1); 
    int mid=l+r>>1;
    return tr[pos]=pull(build(2*pos+1, l, mid), build(2*pos+2, mid+1, r));
}
int sequence(int N, vector<int> a) {
    n=N;
    pos.resize(n+1);
    tr.resize(4*n);
    lazy.resize(4*n);
    for(int i=0; i<n; i++) pos[a[i]].push_back(i);
    int ans=1;
    tr[0]=build();
    for(int val=1; val<=n; val++) {
        int idx=0, SZ=pos[val].size();
        for(int p : pos[val]) update(p, n-1, -1);
        for(int i=0; i<SZ; i++) {
            assert(i<=idx);
            while(idx<SZ) {
                int Min=get(pos[val][idx], n-1).mn;
                if(pos[val][i]) Min-=max(0, get(0, pos[val][i]-1).mx);
                int Max=get(pos[val][idx], n-1).mx;
                if(pos[val][i]) Max-=min(0, get(0, pos[val][i]-1).mn);
                int len=idx-i+1;
                if(Max<(-len) || len<Min) break;
                else idx++;
            }
            ans=max(ans, idx-i);
        }
        for(int p : pos[val]) update(p, n-1, -1);
    }
    return ans;
}

Compilation message

sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:32:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     push(pos); int mid=l+r>>1;
      |                        ~^~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     push(pos); int mid=l+r>>1;
      |                        ~^~
sequence.cpp: In function 'node build(int, int, int)':
sequence.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 630 ms 52816 KB Output is correct
3 Correct 647 ms 52804 KB Output is correct
4 Correct 642 ms 42700 KB Output is correct
5 Correct 684 ms 51784 KB Output is correct
6 Correct 630 ms 51776 KB Output is correct
7 Correct 593 ms 43600 KB Output is correct
8 Correct 663 ms 43572 KB Output is correct
9 Correct 589 ms 43240 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 743 ms 43520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 759 ms 58536 KB Output is correct
2 Correct 768 ms 58524 KB Output is correct
3 Correct 772 ms 57804 KB Output is correct
4 Correct 778 ms 57928 KB Output is correct
5 Correct 770 ms 54524 KB Output is correct
6 Correct 807 ms 54528 KB Output is correct
7 Correct 739 ms 53352 KB Output is correct
8 Correct 723 ms 53036 KB Output is correct

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -