Submission #518311

# Submission time Handle Problem Language Result Execution time Memory
518311 2022-01-23T11:04:19 Z cig32 Financial Report (JOI21_financial) C++17
26 / 100
4000 ms 51320 KB
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define int long long

int st[4*MAXN];

void u(int l, int r, int tar, int idx, int val) {
  if(l == r){
    st[idx] = val;return;
  }
  int mid = (l+r) >> 1;
  if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
  else u(mid+1, r, tar, 2*idx+2, val);
  st[idx] = max(st[2*idx+1], st[2*idx+2]);
}

int qu(int l, int r, int constl, int constr, int idx) {
  if(l<=constl && constr<=r) return st[idx];
  int mid = (constl+constr) >> 1;
  if(mid<l || r<constl) return qu(l, r, mid+1, constr, 2*idx+2);
  if(constr<l || r<mid+1) return qu(l, r, constl, mid, 2*idx+1);
  return max(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}

void update(int i, int v) {
  u(0, MAXN-1, i, 0, v);
}
int query(int l, int r) {
  return qu(l, r, 0, MAXN-1, 0);
}

void solve(int tc) {
  int N,D;cin >> N >> D;
  int A[N+1];
  map<int, vector<int> > mp;
  for(int i=1; i<=N; i++){
    cin>>A[i];
    mp[A[i]].push_back(i);
  }
  
  set<pair<int, int> > s;
  s.insert({300300, 0});
  s.insert({N, N});//actual .first: N+1 - .first
  for(auto xz: mp) {
    int x = xz.first;
    map<int, int> pending;
    for(int y: xz.second) {
      pair<int, int> q = *s.lower_bound({N+1 - y, 0});
      if(q.first == 300300) continue;
//      cout << y << ": ";
//      cout << "erase " << N+1 - q.first << " " << q.second << "\n";
      s.erase(q);
      q.first = N+1 - q.first;
      pair<int, int> q1 = {q.first, y - q.first};
      pair<int, int> q2 = {y + 1, q.first + q.second - 1 - y};
      q1.first = N+1 - q1.first;
      q2.first = N+1 - q2.first;
      if(q1.second >= D) {
        s.insert(q1);
//        cout << "insert " << N+1 - q1.first << " " << q1.second << "\n";
      }
      if(q2.second >= D) {
        s.insert(q2);
//        cout << "insert " << N+1 - q2.first << " " << q2.second << "\n";
      }
    }
    for(int y: xz.second) {
      pair<int, int> q = *s.lower_bound({N+1 - (y - D), 0});
      int lb = 1;
      if(q.first != 300300) {
        lb = N+1 - q.first;
      }
      int q0 = query(lb, y);
      pending[y] = q0 + 1;
    }
    for(auto y: pending) {
      update(y.first, y.second);
    }
  }
  cout << query(1, N) << "\n";
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

Compilation message

Main.cpp: In function 'void solve(long long int)':
Main.cpp:49:9: warning: unused variable 'x' [-Wunused-variable]
   49 |     int x = xz.first;
      |         ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 0 ms 336 KB Output is correct
24 Correct 0 ms 328 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 0 ms 336 KB Output is correct
24 Correct 0 ms 328 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Incorrect 1 ms 336 KB Output isn't correct
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 0 ms 336 KB Output is correct
24 Correct 0 ms 328 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Incorrect 1 ms 336 KB Output isn't correct
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 242 ms 37232 KB Output is correct
2 Correct 290 ms 23432 KB Output is correct
3 Correct 380 ms 21896 KB Output is correct
4 Correct 707 ms 46572 KB Output is correct
5 Correct 497 ms 50040 KB Output is correct
6 Correct 702 ms 51320 KB Output is correct
7 Correct 250 ms 46284 KB Output is correct
8 Correct 257 ms 46504 KB Output is correct
9 Correct 239 ms 46556 KB Output is correct
10 Correct 242 ms 46572 KB Output is correct
11 Correct 410 ms 46856 KB Output is correct
12 Correct 511 ms 47104 KB Output is correct
13 Correct 505 ms 46628 KB Output is correct
14 Correct 588 ms 46948 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 4022 ms 10740 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 0 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 0 ms 336 KB Output is correct
24 Correct 0 ms 328 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Incorrect 1 ms 336 KB Output isn't correct
29 Halted 0 ms 0 KB -