oj.uz

Submission #805064

# Submission time Handle Problem Language Result Execution time Memory
805064 2023-08-03T12:47:20 Z physics07 Comparing Plants (IOI20_plants) C++17
27 / 100
 414 ms 17188 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=200002;
int a[MAX], n;
struct seg{
    pair<int, int> tree[4*MAX];
    int lazy[4*MAX];
    void init(int node, int s, int e) {
        if(s==e) {
            tree[node].second=s;
            return;
        }
        int m=s+e>>1;
        init(node*2, s, m);
        init(node*2+1, m+1, e);
        tree[node]=min(tree[node*2], tree[node*2+1]);
    }
    void lazy_prop(int node, int s, int e) {
        tree[node].first+=lazy[node];
        if(s!=e) {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    void update(int node, int s, int e, int l, int r, int v) {
        lazy_prop(node, s, e);
        if(s>r || e<l) return;
        if(s>=l && e<=r) {
            lazy[node]+=v;
            lazy_prop(node, s, e);
            return;
        }
        int m=s+e>>1;
        update(node*2, s, m, l, r, v);
        update(node*2+1, m+1, e, l, r, v);
        tree[node]=min(tree[node*2], tree[node*2+1]);
    }
    pair<int, int> query(int node, int s, int e, int l, int r) {
        lazy_prop(node, s, e);
        if(s>r || e<l) return make_pair(1e9, 0);
        if(s>=l && e<=r) return tree[node];
        int m=s+e>>1;
        return min(query(node*2, s, m, l, r), query(node*2+1, m+1, e, l, r));
    }
} tree;
void init(int k, vector<int> r) {
    n=(int)r.size();
    tree.init(1, 0, n-1);
    for(int i=0; i<n; i++) tree.update(1, 0, n-1, i, i, r[i]);
    for(int i=0; i<n; i++) {
        int idx=tree.query(1, 0, n-1, 0, n-1).second;
        if(idx>=k-1) {
            pair<int, int> curr=tree.query(1, 0, n-1, idx-k+1, idx-1);
            if(curr.first==0) idx=curr.second;
        }
        else {
            pair<int, int> x=tree.query(1, 0, n-1, 0, idx-1), y=tree.query(1, 0, n-1, idx-k+1+n, n-1);
            if(y.first==0) idx=y.second;
            else if(x.first==0) idx=x.second;
        }
        a[idx]=i;
        tree.update(1, 0, n-1, idx, idx, k);
        if(idx>=k-1) tree.update(1, 0, n-1, idx-k+1, idx-1, -1);
        else {
            tree.update(1, 0, n-1, 0, idx-1, -1);
            tree.update(1, 0, n-1, idx-k+1+n, n-1, -1);
        }
    }
}

int compare_plants(int x, int y) {
    if(a[x]<a[y]) return 1;
    else return -1;
}

Compilation message

plants.cpp: In member function 'void seg::init(int, int, int)':
plants.cpp:15:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |         int m=s+e>>1;
      |               ~^~
plants.cpp: In member function 'void seg::update(int, int, int, int, int, int)':
plants.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int m=s+e>>1;
      |               ~^~
plants.cpp: In member function 'std::pair<int, int> seg::query(int, int, int, int, int)':
plants.cpp:45:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int m=s+e>>1;
      |               ~^~

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 49 ms 11328 KB Output is correct
8 Correct 4 ms 6584 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 48 ms 11364 KB Output is correct
11 Correct 53 ms 11216 KB Output is correct
12 Correct 47 ms 11468 KB Output is correct
13 Correct 49 ms 11320 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 49 ms 11328 KB Output is correct
8 Correct 4 ms 6584 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 48 ms 11364 KB Output is correct
11 Correct 53 ms 11216 KB Output is correct
12 Correct 47 ms 11468 KB Output is correct
13 Correct 49 ms 11320 KB Output is correct
14 Correct 70 ms 12112 KB Output is correct
15 Correct 414 ms 17036 KB Output is correct
16 Correct 69 ms 12056 KB Output is correct
17 Correct 375 ms 17028 KB Output is correct
18 Correct 274 ms 16516 KB Output is correct
19 Correct 277 ms 17188 KB Output is correct
20 Correct 400 ms 17092 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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