oj.uz

Submission #1046181

# Submission time Handle Problem Language Result Execution time Memory
1046181 2024-08-06T11:14:00 Z nightfal Comparing Plants (IOI20_plants) C++14
19 / 100
 1054 ms 268484 KB 
// #include "plants.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <utility>
#include <algorithm>

// using namespace std;
#define maxVal 1'000'000'001
static std:: vector<int> rank,lz,lzr;
static std:: vector<std::pair<int,int>> t,tr;
static std:: vector<std::vector<int>> g;
static std:: vector<std::vector<std::vector<int>>> power;

static int l,m;
void print(std::pair<int,int> p) {std::cout << "(" << p.first << "," << p.second << ") "; };
void print(std::vector<int> &v) {for(int elem: v) std::cout << elem << " "; std::cout << std::endl;}
void print(std::vector<std::vector<int>> &v) {for (auto elem: v) print(elem); std::cout << std::endl;}
void print(std::vector<std::pair<int,int>> &v) {for(auto [a,b]: v) std::cout << "(" << a << "," << b << ") ";std::cout << std::endl;}
void print(std::vector<std::vector<std::vector<int>>> &v) {for (auto elem: v) print(elem); std::cout << std::endl;}

std::pair<int,int> update(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int node,int start,int end,int left,int right,int diff) {
    if (left <= start and end <= right) lz[node] += diff;
    if (start!=end) { lz[2*node] += lz[node]; lz[2*node+1] += lz[node];}
    t[node].first += lz[node]; lz[node]=0;
    if (right < start or end < left) return {maxVal,m+1};
    if (left <= start and end <= right) return t[node];

    int mid=(start+end)/2;
    auto ans1  = update(t,lz,2*node,start,mid,left,right,diff);
    auto ans2  = update(t,lz,2*node+1,mid+1,end,left,right,diff);
    auto ans = std::min(ans1,ans2);
    t[node] = std::min(t[2*node],t[2*node+1]);
    return ans;    
}
std::pair<int,int> findMin(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int node, int start, int end, int left, int right) {
    if (start!=end) {lz[2*node] += lz[node]; lz[2*node+1] += lz[node];}
    t[node].first += lz[node]; lz[node]=0;
    if (right < start or end < left) return {maxVal,m+1};
    if (left <= start and end <= right) return t[node];
    
    int mid=(start+end)/2;
    auto min1 = findMin(t,lz,2*node,start,mid,left,right);
    auto min2 = findMin(t,lz,2*node+1,mid+1,end,left,right);
    auto ans = std::min(min1,min2);
    t[node] = std::min(t[2*node],t[2*node+1]);    
    return ans;
}
void segInit(std::vector<int> &r, std::vector<std::pair<int,int>> &t, int node, int start, int end) {
    if (start==end) {t[node]={r[start],start}; return;}
    int mid=(start+end)/2;
    segInit(r,t, 2*node,start,mid);
    segInit(r,t, 2*node+1,mid+1,end);
    t[node] = std::min(t[2*node],t[2*node+1]);
    return;
}
int findPreMinI(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int k,int minI1) {
    int ans = minI1;
    if (minI1>0) {
        auto [min2,minI2] = findMin(t,lz,1,0,m-1,std::max(0,minI1-k+1),minI1-1);
        if (min2==0) ans = minI2;
    }
    if (minI1-k+1<0) {
        auto [min2,minI2] = findMin(t,lz,1,0,m-1,minI1-k+1+m,m-1);
        if (min2==0) ans = minI2;
    }
    return ans;
}
int computeRank(std::vector<std::pair<int,int>> &t, std::vector<int> &lz, int minI1, int k, int ranking) {

    if (rank[minI1]!=m) return ranking;
    int minI2 = findPreMinI(t,lz,k,minI1);

    while (minI2 != minI1) {
        ranking = computeRank(t,lz,minI2,k,ranking); 
        minI2 = findPreMinI(t,lz,k,minI1);
    }
    rank[minI1] = ranking--;
    update(t,lz,1,0,m-1,minI1,minI1,m-1);
    if(minI1>0) update(t,lz,1,0,m-1,std::max(0,minI1-k+1),minI1-1,-1);
    if(minI1-k+1<0) update(t,lz,1,0,m-1,minI1-k+1+m,m-1,-1);

    return ranking;
}

bool inRangeLeft(int z, int y, int left) {return y < z && (z < left || left <= y) || z < y && (z < left && left <= y);}
bool inRangeRight(int z, int y, int right) {return z < y && (right < z || y <= right) || y < z && (y <= right && right < z);}

int compare(int x, int y) {
    int left, i=0, z=x;
    while(true) {
        left = power[i][z][0];
        if(left==-1 || inRangeLeft(z,y,left)) break;
        i++;
    }
    for(int j=i-1; j>=0; j--) {
        left = power[j][z][0];
        if (left!=-1 && !inRangeLeft(z,y,left)) z = left; 
    }
    left = power[0][z][0];
    if (left!=-1 && inRangeLeft(z,y,left) && -rank[z]>-rank[y]) return 1;

    int right; 
    i=0; z= x;
    while(true) {
        right = power[i][z][1];
        if(right==-1 || inRangeRight(z,y,right)) break;
        i++;
    }
    for(int j=i-1; j>=0; j--) {
        right = power[j][z][1];
        if(right!=-1 && !inRangeRight(z,y,right)) z = right;
    }
    right = power[0][z][1];
    if(right!=-1 && inRangeRight(z,y,right) && -rank[z]>-rank[y]) return 1;

    return 0;
}
void calPower() {
    int x = m-1, cnt=1;
    while (x) {x>>=1; cnt++;}
    cnt++;
    power.resize(cnt,std::vector<std::vector<int>>(m,std::vector<int>(2,-1)));
    for(int j=0; j<m; j++)
        for(int x=0; x<2; x++)
            power[0][j][x] = g[j][x];
    
    for (int i=1; i<cnt; i++)
        for(int j=0; j<m; j++)
            for(int x=0; x<2; x++) {
                if (power[i-1][j][x] == -1) power[i][j][x] = -1;
                else power[i][j][x] = power[i-1][power[i-1][j][x]][x];
            }
    // std::cout << "rank: "<<std::endl; print(rank);
    // std::cout << "power: "<<std::endl; print(power);
    // std::cout << "rangeLR: "<<std::endl; print(rangeLR);
}
void calReachability(int k) {
    tr.resize(4*m); lzr.resize(4*m);
    std::vector<std::pair<int,int>> rankInv;
    for(int i=0; i<m; i++) {rank[i] = -rank[i]; rankInv.push_back({rank[i],i}); }
    sort(rankInv.begin(),rankInv.end());
    segInit(rank,tr,1,0,m-1);

    g.resize(m,std::vector<int>(2,-1));
    
    for(auto [val,i]: rankInv) {
        std::pair<int,int> temp1 ={maxVal,m+1}, temp2={maxVal,m+1};
        if (i>0) temp1 = findMin(tr,lzr,1,0,m-1,std::max(0,i-k+1),i-1);
        if (i-k+1<0) temp2 = findMin(tr,lzr,1,0,m-1,i-k+1+m,m-1);
        temp1 = std::min(temp1,temp2); 
        if (temp1.first <=0) g[i][0] = temp1.second;

        temp1 ={maxVal,m+1}, temp2={maxVal,m+1};
        if (i+1<m) temp1 = findMin(tr,lzr,1,0,m-1,i+1,std::min(m-1,i+k-1));
        if (i+k-1>m-1) temp2 = findMin(tr,lzr,1,0,m-1,0,i+k-1-m);
        temp1 = std::min(temp1,temp2);
        if (temp1.first <= 0) g[i][1] = temp1.second;
        update(tr,lzr,1,0,m-1,i,i,m);
    }

    calPower();
    return;
}
void init6(int k, std::vector<int> &r) {
    int n = r.size(); 
    t.resize(4*n); lz.resize(4*n); 
    segInit(r,t,1,0,n-1);
    rank.resize(n,n);
    int ranking = n-1;
    while (ranking >=0) {
        auto [min1,minI1] = findMin(t,lz,1,0,n-1,0,n-1);
        ranking = computeRank(t,lz,minI1,k,ranking);
    }
    calReachability(k);
    return;
}

void init(int k, std::vector<int> r) {
    int n = r.size(); 
    m=n; l=k;
    init6(k,r);
	return;
}
int compare_plants(int x, int y) {
    int ans = compare(x,y);
    if (ans) return ans;
    else return -compare(y,x);
}

Compilation message

plants.cpp: In function 'void print(std::vector<std::pair<int, int> >&)':
plants.cpp:20:58: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 | void print(std::vector<std::pair<int,int>> &v) {for(auto [a,b]: v) std::cout << "(" << a << "," << b << ") ";std::cout << std::endl;}
      |                                                          ^
plants.cpp: In function 'int findPreMinI(std::vector<std::pair<int, int> >&, std::vector<int>&, int, int)':
plants.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         auto [min2,minI2] = findMin(t,lz,1,0,m-1,std::max(0,minI1-k+1),minI1-1);
      |              ^
plants.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [min2,minI2] = findMin(t,lz,1,0,m-1,minI1-k+1+m,m-1);
      |              ^
plants.cpp: In function 'bool inRangeLeft(int, int, int)':
plants.cpp:87:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   87 | bool inRangeLeft(int z, int y, int left) {return y < z && (z < left || left <= y) || z < y && (z < left && left <= y);}
      |                                                  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
plants.cpp: In function 'bool inRangeRight(int, int, int)':
plants.cpp:88:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   88 | bool inRangeRight(int z, int y, int right) {return z < y && (right < z || y <= right) || y < z && (y <= right && right < z);}
      |                                                    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
plants.cpp: In function 'void calReachability(int)':
plants.cpp:148:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |     for(auto [val,i]: rankInv) {
      |              ^
plants.cpp: In function 'void init6(int, std::vector<int>&)':
plants.cpp:173:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |         auto [min1,minI1] = findMin(t,lz,1,0,n-1,0,n-1);
      |              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 29 ms 3260 KB Output is correct
7 Correct 115 ms 25804 KB Output is correct
8 Correct 491 ms 266432 KB Output is correct
9 Correct 557 ms 266436 KB Output is correct
10 Correct 632 ms 266436 KB Output is correct
11 Correct 731 ms 266436 KB Output is correct
12 Correct 806 ms 266380 KB Output is correct
13 Correct 872 ms 266556 KB Output is correct
14 Correct 985 ms 266436 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 4 ms 1372 KB Output is correct
7 Correct 64 ms 8272 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 64 ms 8264 KB Output is correct
11 Correct 71 ms 8272 KB Output is correct
12 Correct 115 ms 8520 KB Output is correct
13 Correct 62 ms 8288 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 4 ms 1372 KB Output is correct
7 Correct 64 ms 8272 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 64 ms 8264 KB Output is correct
11 Correct 71 ms 8272 KB Output is correct
12 Correct 115 ms 8520 KB Output is correct
13 Correct 62 ms 8288 KB Output is correct
14 Correct 128 ms 25808 KB Output is correct
15 Correct 892 ms 266436 KB Output is correct
16 Incorrect 128 ms 25808 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 74 ms 4924 KB Output is correct
4 Correct 1054 ms 267968 KB Output is correct
5 Incorrect 999 ms 266684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 1 ms 348 KB Output is correct
7 Correct 10 ms 1116 KB Output is correct
8 Incorrect 10 ms 1112 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 2 ms 1116 KB Output is correct
6 Correct 688 ms 266568 KB Output is correct
7 Correct 820 ms 266568 KB Output is correct
8 Correct 756 ms 266548 KB Output is correct
9 Correct 877 ms 266568 KB Output is correct
10 Correct 695 ms 266948 KB Output is correct
11 Correct 747 ms 266436 KB Output is correct
12 Correct 728 ms 268484 KB Output is correct
13 Correct 777 ms 266692 KB Output is correct
14 Incorrect 800 ms 266596 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 29 ms 3260 KB Output is correct
7 Correct 115 ms 25804 KB Output is correct
8 Correct 491 ms 266432 KB Output is correct
9 Correct 557 ms 266436 KB Output is correct
10 Correct 632 ms 266436 KB Output is correct
11 Correct 731 ms 266436 KB Output is correct
12 Correct 806 ms 266380 KB Output is correct
13 Correct 872 ms 266556 KB Output is correct
14 Correct 985 ms 266436 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 4 ms 1372 KB Output is correct
21 Correct 64 ms 8272 KB Output is correct
22 Correct 2 ms 344 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 64 ms 8264 KB Output is correct
25 Correct 71 ms 8272 KB Output is correct
26 Correct 115 ms 8520 KB Output is correct
27 Correct 62 ms 8288 KB Output is correct
28 Correct 128 ms 25808 KB Output is correct
29 Correct 892 ms 266436 KB Output is correct
30 Incorrect 128 ms 25808 KB Output isn't correct
31 Halted 0 ms 0 KB -