oj.uz

Submission #989039

# Submission time Handle Problem Language Result Execution time Memory
989039 2024-05-27T10:39:45 Z AdamGS Comparing Plants (IOI20_plants) C++17
0 / 100
 5 ms 4808 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7;
pair<int,int>tr[4*LIM];
int lazy[4*LIM], T[LIM], n, k, N=1;
void spl(int v) {
  tr[2*v].st+=lazy[v];
  tr[2*v+1].st+=lazy[v];
  lazy[2*v]+=lazy[v];
  lazy[2*v+1]+=lazy[v];
  lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
  if(r<a || b<l) return;
  if(a<=l && r<=b) {
    tr[v].st+=x;
    lazy[v]+=x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=min(tr[2*v], tr[2*v+1]);
}
pair<int,int>cnt(int v, int l, int r, int a, int b) {
  if(r<a || b<l) return {INF, INF};
  if(a<=l && r<=b) return tr[v];
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  return min(cnt(2*v, l, mid, a, b), cnt(2*v+1, mid+1, r, a, b));
}
int znajdz(int x) {
  upd(1, 0, N-1, x-k+1, x, -1);
  if(x-k+1<0) upd(1, 0, N-1, n+x-k+1, n-1, -1);
  upd(1, 0, N-1, x, x, INF);
  pair<int,int>a=cnt(1, 0, N-1, x+1, n-1);
  if(a.st==0) return a.nd;
  return cnt(1, 0, N-1, 0, x-1).nd;
}
void init(int _k, vector<int>r) {
  n=r.size(); k=_k;
  while(N<n) N*=2;
  rep(i, n) tr[N+i]={r[i], i};
  for(int i=N-1; i; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
  int lst=-1, akt=-1;
  for(int i=n-1; i>=0; --i) if(r[i]==0) lst=i;
  for(int i=lst+1; i<n; ++i) if(r[i]==0) {
    if(i-lst>k-1) {
      akt=i;
      break;
    }
    lst=i;
  }
  rep(i, n) if(r[i]==0 && akt==-1) akt=i;
  T[akt]=n-1;
  for(int i=n-2; i>=0; --i) {
    akt=znajdz(akt);
    T[akt]=i;
  }
}
int compare_plants(int x, int y) {
	if(T[x]>T[y]) return 1;
  return -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Runtime error 5 ms 4808 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Runtime error 5 ms 4808 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Runtime error 2 ms 4696 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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