oj.uz

Submission #57550

# Submission time Handle Problem Language Result Execution time Memory
57550 2018-07-15T08:40:20 Z 강태규(#1669) Teams (CEOI11_tea) C++11
0 / 100
 872 ms 90120 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 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(-1, -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:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
tea.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23764 KB Output is correct
2 Incorrect 25 ms 23912 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 20]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 23964 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 100]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 24040 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 200]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 24328 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 4999]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 24404 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 5000]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 28856 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 80005]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 30336 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 90003]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 796 ms 80112 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 750013]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 872 ms 90120 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 1000000]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 780 ms 90120 KB Integer parameter [name=k_j] equals to 0, violates the range [1, 1000000]
2 Halted 0 ms 0 KB -