oj.uz

Submission #57551

# Submission time Handle Problem Language Result Execution time Memory
57551 2018-07-15T08:43:44 Z 강태규(#1669) Teams (CEOI11_tea) C++11
100 / 100
 1025 ms 104200 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int inf = 1e7;
int n;
pii a[1000001];
pii seg[1 << 21];
int cnt[1000001];
int pr[1000001];
int sz[1000001];

void init(int i, int s, int e) {
    seg[i] = pii(-inf, e);
    if (s == e) return;
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
}

void update(int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[i] = pii(v, x);
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i << 1, s, m, x, v);
    else update(i << 1 | 1, m + 1, e, x, v);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

pii query(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return pii(-inf, -1);
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return max(query(i << 1, s, m, x, y), query(i << 1 | 1, m + 1, e, x, y));
}

vector<pii> querys[1000001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        a[i] = pii(x, i);
    }
    sort(a + 1, a + (n + 1));
    update(1, 0, n, 0, 0);
    for (int i = 1; i <= n; ++i) {
        for (pii j : querys[i]) update(1, 0, n, j.first, j.second);
        int x = i - a[i].first;
        tie(cnt[i], pr[i]) = query(1, 0, n, 0, x);
        ++cnt[i];
        int p = i + i - pr[i];
        if (p <= n) querys[p].emplace_back(i, cnt[i]);
    }
    vector<pii> ans;
    for (int i = n; i > 0; i = pr[i]) {
        ans.emplace_back(pr[i], i);
    }
    printf("%d\n", (int)ans.size());
    for (pii i : ans) {
        printf("%d", i.second - i.first);
        for (int j = i.first + 1; j <= i.second; ++j) {
            printf(" %d", a[j].second);
        }
        printf("\n");
    }
	return 0;
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
tea.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 25 ms 24036 KB Output is correct
3 Correct 22 ms 24036 KB Output is correct
4 Correct 22 ms 24036 KB Output is correct
5 Correct 24 ms 24036 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24036 KB Output is correct
2 Correct 23 ms 24036 KB Output is correct
3 Correct 28 ms 24060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24060 KB Output is correct
2 Correct 21 ms 24060 KB Output is correct
3 Correct 27 ms 24060 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24396 KB Output is correct
2 Correct 31 ms 24424 KB Output is correct
3 Correct 32 ms 24440 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24460 KB Output is correct
2 Correct 27 ms 24476 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28952 KB Output is correct
2 Correct 82 ms 30468 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 30468 KB Output is correct
2 Correct 85 ms 30468 KB Output is correct
3 Correct 100 ms 30468 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 80192 KB Output is correct
2 Correct 812 ms 81260 KB Output is correct
3 Correct 645 ms 81260 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 87092 KB Output is correct
2 Correct 913 ms 104200 KB Output is correct
3 Correct 868 ms 104200 KB Output is correct
4 Correct 996 ms 104200 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 104200 KB Output is correct
2 Correct 592 ms 104200 KB Output is correct
3 Correct 1012 ms 104200 KB Output is correct
4 Correct 1025 ms 104200 KB Output is correct