Submission #47366

#	Time	Username	Problem	Language	Result	Execution time	Memory
47366		tieunhi	새로운 문제 (POI11_pio)	C++14	54 / 100	428 ms	12744 KiB

pio

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define maxc 1000000007
#define N 500005
using namespace std;

struct Dequeue
{
    int a[N];
    int top, bot;
    Dequeue()
    {
        bot = 0;
        top = 1;
    }
    void push_back(int x) {a[++bot] = x;}
    void pop_back() {bot--;}
    void pop_front() {top++;}
    int back() {return a[bot];}
    int front() {return a[top];}
    bool empty() {return (bot < top);}
}q;
int n, a[N], x2[N], res[N], delta[N];

void inline MAX(int &A, int B) {A = max(A, B);}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= sqrt(n) + 1; i++)
        x2[i] = i*i;
    for (int i = 1; i <= sqrt(n) + 1; i++)
        delta[i] = x2[i] - x2[i-1];

    for (int can = 1; can <= sqrt(n)+1; can++)
    {
        int len = delta[can];
        while (!q.empty()) q.pop_back();
        for (int i = 1; i <= n; i++)
        {
            int pos = i - x2[can-1] - 1;
            while (!q.empty() && q.front() <= pos - len)
                q.pop_front();

            if (pos > 0)
            {
                while (!q.empty() && a[q.back()] <= a[pos])
                    q.pop_back();
                q.push_back(pos);
            }
            if (!q.empty()) MAX(res[i], a[q.front()] + can);
        }

        while (!q.empty()) q.pop_back();
        for (int i = n; i >= 1; i--)
        {
            int pos = i + x2[can-1] + 1;
            while (!q.empty() && q.front() >= pos + len)
                q.pop_front();

            if (pos <= n)
            {
                while (!q.empty() && a[q.back()] <= a[pos])
                    q.pop_back();
                q.push_back(pos);
            }
            if (!q.empty()) MAX(res[i], a[q.front()] + can);
        }
    }
    for (int i = 1; i <= n; i++)
        if (res[i] <= a[i]) cout <<0<<'\n';
        else cout <<res[i] - a[i]<<'\n';

}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10