oj.uz

Submission #902575

# Submission time Handle Problem Language Result Execution time Memory
902575 2024-01-10T18:23:37 Z qin Financial Report (JOI21_financial) C++17
5 / 100
 387 ms 34848 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18;
int base = 1;
struct seg{
		vector<int> t;
		void init(int n){
				while(base < n) base <<= 1;
				t.resize(base<<1);
		}
		void update(int i, int val){
				for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = max(t[i<<1], t[i<<1|1]);
		}
		int query(int i, int s, int e, int x, int y){
				if(x <= s && e <= y) return t[i];
				int mid = (s+e)>>1, ret = 0;
				if(x <= mid) ret = max(ret, query(i<<1, s, mid, x, y));
				if(mid < y) ret = max(ret, query(i<<1|1, mid+1, e, x, y));
				return ret;
		}
		int qr(int x, int y){
				if(x <= y) return query(1, 1, base, max(1, x), min(base, y));
				return 0;
		}
};
void answer(){
		int n, d; scanf("%d%d", &n, &d);
		set<int> sc;
		vector<int> t(n+1);
		for(int i = 1; i <= n; ++i) scanf("%d", &t[i]), sc.emplace(t[i]);
		unordered_map<int, int> mp; int it = 0;
		for(int u : sc) mp[u] = ++it;
		for(int i = 1; i <= n; ++i) t[i] = mp[t[i]];
		seg seg; seg.init(n+1);
		for(int i = 1; i < n; ++i) seg.update(t[i], seg.qr(1, t[i]-1)+1);
		printf("%d\n", max(seg.qr(1, t[n]-1)+1, seg.qr(t[n], base))); 
}
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message

Main.cpp: In function 'void answer()':
Main.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   int n, d; scanf("%d%d", &n, &d);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:37:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   for(int i = 1; i <= n; ++i) scanf("%d", &t[i]), sc.emplace(t[i]);
      |                               ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 344 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 344 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 344 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8532 KB Output is correct
2 Correct 80 ms 8272 KB Output is correct
3 Incorrect 99 ms 8624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8924 KB Output is correct
2 Correct 95 ms 8528 KB Output is correct
3 Correct 102 ms 8932 KB Output is correct
4 Correct 314 ms 34748 KB Output is correct
5 Correct 324 ms 34844 KB Output is correct
6 Correct 387 ms 34848 KB Output is correct
7 Correct 166 ms 34620 KB Output is correct
8 Correct 151 ms 34784 KB Output is correct
9 Correct 197 ms 34508 KB Output is correct
10 Correct 263 ms 34756 KB Output is correct
11 Correct 311 ms 34600 KB Output is correct
12 Correct 328 ms 34664 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 344 KB Output isn't correct
13 Halted 0 ms 0 KB -