oj.uz

Submission #70982

# Submission time Handle Problem Language Result Execution time Memory
70982 2018-08-24T00:44:24 Z 강태규(#2201) Global Warming (CEOI18_glo) C++11
0 / 100
 176 ms 3816 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;

int n, x, m;
int t[200001];
int dp[200001][2];
int cp[200000];

int find(int x) {
    return lower_bound(cp, cp + m, x) - cp + 1;
}

int seg0[200001];
int seg1[200001];
void update(int seg[], int i, int x) {
    while (i <= m) {
        seg[i] = max(seg[i], x);
        i += i & -i;
    }
}

int query(int seg[], int i) {
    int ret = 0;
    while (i) {
        ret = max(ret, seg[i]);
        i -= i & -i;
    }
    return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	scanf("%d%d", &n, &x);
	for (int i = 1; i <= n; ++i) {
        scanf("%d", t + i);
        cp[i - 1] = t[i];
	}
	sort(cp, cp + n);
	m = unique(cp, cp + n) - cp;
	for (int i = 1; i <= n; ++i) {
        int pr0 = find(t[i]);
        int pr1 = find(t[i] + x) - 1;
        int dp0 = query(seg0, pr0 - 1) + 1;
        int dp1 = max(query(seg0, pr1), query(seg1, pr0)) + 1;
        update(seg0, pr0, dp0);
        update(seg1, pr0, dp1);
	}
	printf("%d\n", max(query(seg0, m), query(seg1, m)));
	return 0;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &x);
  ~~~~~^~~~~~~~~~~~~~~~
glo.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", t + i);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 3592 KB Output is correct
2 Correct 168 ms 3684 KB Output is correct
3 Correct 168 ms 3816 KB Output is correct
4 Correct 176 ms 3816 KB Output is correct
5 Incorrect 78 ms 3816 KB Output isn't correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3816 KB Output is correct
2 Correct 40 ms 3816 KB Output is correct
3 Correct 39 ms 3816 KB Output is correct
4 Incorrect 33 ms 3816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3816 KB Output is correct
2 Correct 71 ms 3816 KB Output is correct
3 Correct 146 ms 3816 KB Output is correct
4 Incorrect 82 ms 3816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -