oj.uz

Submission #47368

# Submission time Handle Problem Language Result Execution time Memory
47368 2018-05-01T16:47:05 Z tieunhi Lightning Conductor (POI11_pio) C++14
63 / 100
 1000 ms 6548 KB 
#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 510005
using namespace std;

struct Dequeue
{
    int a[N];
    int top, bot;
    void clear() {top = 1; bot = 0;}
    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 readInt () {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}
int main()
{
    //freopen("INP.TXT", "r", stdin);
    n = readInt();
    for (int i = 1; i <= n; i++)
        a[i] = readInt();
    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];
        q.clear();
        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);
        }

        q.clear();
        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]) printf("0\n");
        else printf("%d\n", res[i] - a[i]);

}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 1176 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 1552 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 1644 KB Output is correct
2 Correct 135 ms 1660 KB Output is correct
3 Correct 375 ms 1892 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 2172 KB Output is correct
2 Correct 638 ms 2172 KB Output is correct
3 Correct 710 ms 2804 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 3316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 4756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 6548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 6548 KB Time limit exceeded
2 Halted 0 ms 0 KB -