oj.uz

Submission #815273

# Submission time Handle Problem Language Result Execution time Memory
815273 2023-08-08T13:48:58 Z lkh3happy Comparing Plants (IOI20_plants) C++14
44 / 100
 756 ms 16848 KB 
#include "plants.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <assert.h>
using namespace std;

int r[222222], lz[888888], rnk[222222], k;
pair<int, int> t[888888];

void scl(int l, int r, int n){
    lz[n]=0;
    if(l==r){
        t[n]={0, l};
        return;
    }
    int m=l+r>>1;
    scl(l, m, n*2); scl(m+1, r, n*2+1);
    t[n]=min(t[n*2], t[n*2+1]);
}

void lzup(int l, int r, int n){
    t[n].first+=lz[n];
    if(l^r) lz[n*2]+=lz[n], lz[n*2+1]+=lz[n];
    lz[n]=0;
}

void upd(int l, int r, int n, int s, int e, int x){
    lzup(l, r, n);
    if(r<s || e<l) return;
    if(s<=l && r<=e){
        lz[n]+=x;
        lzup(l, r, n);
        return;
    }
    int m=l+r>>1;
    upd(l, m, n*2, s, e, x); upd(m+1, r, n*2+1, s, e, x);
    t[n]=min(t[n*2], t[n*2+1]);
}

pair<int, int> mn(int l, int r, int n, int s, int e){
    lzup(l, r, n);
    if(r<s || e<l) return {1e9, 1e9};
    if(s<=l && r<=e) return t[n];
    int m=l+r>>1;
    return min(mn(l, m, n*2, s, e), mn(m+1, r, n*2+1, s, e));
}

pair<int, int> fmn(int l, int r, int n, int s, int e){
    if(e<1) return mn(l, r, n, r+s, r+e);
    if(s>r) return mn(l, r, n, s-r, e-r);
    if(e>r){
        pair<int, int> x=mn(l, r, n, s, r);
        if(!x.first) return x;
        return min(x, mn(l, r, n, 1, e-r));
    }
    if(s<1){
        pair<int, int> x=mn(l, r, n, r+s, r);
        if(!x.first) return x;
        return min(mn(l, r, n, 1, e), x);
    }
    return mn(l, r, n, s, e);
}

void fupd(int l, int r, int n, int s, int e, int x){
    if(s>0 && e<=r) return upd(l, r, n, s, e, x);
    if(e<1) return upd(l, r, n, r+s, r+e, x);
    if(s>r) return upd(l, r, n, s-r, e-r, x);
    if(e>r) return upd(l, r, n, s, r, x), upd(l, r, n, 1, e-r, x);
    if(s<1) return upd(l, r, n, 1, e, x), upd(l, r, n, r+s, r, x);
}

void init(int _k, vector<int> _r){
    int n=_r.size(), k=_k;
    scl(1, n, 1);
    vector<int> v;
    for(int i=1;i<=n;i++) r[i]=_r[i-1], upd(1, n, 1, i, i, r[i]);
    for(int i=1;i<=n;i++) if(!r[i] && fmn(1, n, 1, i-k+1, i-1).first) rnk[i]=1, v.push_back(i);
    for(int i=0;i<v.size();i++){
        fupd(1, n, 1, v[i]-k+1, v[i]-1, -1); fupd(1, n, 1, v[i], v[i], 1e9);
        pair<int, int> lx=fmn(1, n, 1, v[i]-k+1, v[i]-1), rx=fmn(1, n, 1, v[i]+1, v[i]+k-1);
        if(!lx.first && fmn(1, n, 1, lx.second-k+1, lx.second-1).first && !rnk[lx.second])  rnk[lx.second]=rnk[v[i]]+1, v.push_back(lx.second);
        if(!rx.first && fmn(1, n, 1, rx.second-k+1, rx.second-1).first && !rnk[rx.second]) rnk[rx.second]=rnk[v[i]]+1, v.push_back(rx.second);
    }
	return;
}

int compare_plants(int x, int y){
    x++; y++;
	return (rnk[x]>rnk[y])?-1:1;
}

Compilation message

plants.cpp: In function 'void scl(int, int, int)':
plants.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     int m=l+r>>1;
      |           ~^~
plants.cpp: In function 'void upd(int, int, int, int, int, int)':
plants.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int m=l+r>>1;
      |           ~^~
plants.cpp: In function 'std::pair<int, int> mn(int, int, int, int, int)':
plants.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int m=l+r>>1;
      |           ~^~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 300 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 0 ms 288 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 3 ms 400 KB Output is correct
7 Correct 49 ms 5332 KB Output is correct
8 Correct 2 ms 308 KB Output is correct
9 Correct 4 ms 452 KB Output is correct
10 Correct 49 ms 5352 KB Output is correct
11 Correct 46 ms 5196 KB Output is correct
12 Correct 46 ms 5476 KB Output is correct
13 Correct 48 ms 5344 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 3 ms 400 KB Output is correct
7 Correct 49 ms 5332 KB Output is correct
8 Correct 2 ms 308 KB Output is correct
9 Correct 4 ms 452 KB Output is correct
10 Correct 49 ms 5352 KB Output is correct
11 Correct 46 ms 5196 KB Output is correct
12 Correct 46 ms 5476 KB Output is correct
13 Correct 48 ms 5344 KB Output is correct
14 Correct 85 ms 6548 KB Output is correct
15 Correct 625 ms 16788 KB Output is correct
16 Correct 89 ms 6552 KB Output is correct
17 Correct 616 ms 16796 KB Output is correct
18 Correct 517 ms 16116 KB Output is correct
19 Correct 460 ms 16544 KB Output is correct
20 Correct 623 ms 16848 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 42 ms 4880 KB Output is correct
4 Correct 384 ms 15940 KB Output is correct
5 Correct 472 ms 16016 KB Output is correct
6 Correct 528 ms 16356 KB Output is correct
7 Correct 713 ms 16572 KB Output is correct
8 Correct 756 ms 16812 KB Output is correct
9 Correct 443 ms 15864 KB Output is correct
10 Correct 417 ms 16104 KB Output is correct
11 Correct 359 ms 15716 KB Output is correct
12 Correct 378 ms 15956 KB Output is correct
13 Correct 511 ms 15940 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 300 KB Output isn't correct
5 Halted 0 ms 0 KB -