제출 #930060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930060		heavylightdecomp	Sequence (APIO23_sequence)	C++17	28 / 100	2056 ms	33252 KiB

sequence

#include<bits/stdc++.h>
#include "sequence.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
#define vt vector
#define f0r(i,a,b) for(auto i =(a); i != (b); i++)
#define r0f(i,a,b) for(auto i =(a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
// sim dor ris eni(x) rge range dud debug 2eni 2dor
#define sim template< class c
#define dor > debug& operator<<
#define ris return *this
#define eni(x) sim> typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i)
sim> struct rge { c b,e; };
sim> rge<c> range(c i, c j) {
    return rge<c>{i,j};
}
sim> auto dud(c *x)->decltype(cout << *x, 0);
sim> char dud(...);
struct debug {
    ~debug() { cerr << endl; }
    eni(!=) { cerr << boolalpha << i; ris; }
    eni(==) { ris << range(all(i)); }
    sim, class b dor(pair<b,c> d) {
        ris << "(" << d.X << ", " << d.Y << ")";
    }
    sim dor(rge<c> d) {
        *this << "{";
        f0r(i,d.b,d.e) *this << ", "+2*(i==d.b) << *i;
        ris << "}";
    }
};
#define imie(r...) " [" << #r << ": " << (r) << "] "
struct median {
    priority_queue<int> a;
    priority_queue<int, vt<int>, greater<int>> b;
    void ins(int k) {
        a.push(k);
        int have = sz(a)+sz(b);
        while(sz(a) > have/2) {
            b.push(a.top());
            a.pop();
        }
        while(sz(b) > have/2) {
            a.push(b.top());
            b.pop();
        }
    }
    pii get() {
        assert(sz(a));
        int have = sz(a) + sz(b);
        if(have % 2) return {a.top(), a.top()};
        else return {a.top(), b.top()};
    }
};

int sequence(int n, vt<int> ar) {

    map<int,int> freq;
    int res = 0;
    f0r(l,0,n) {
        median ds;
        freq.clear();
        f0r(r,l,n) {
            freq[ar[r]]++;
            ds.ins(ar[r]);
            pii hmm = ds.get();
            res = max({res, freq[hmm.X], freq[hmm.Y]});
        }
    }
    return res;

}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18