oj.uz

Submission #1046177

# Submission time Handle Problem Language Result Execution time Memory
1046177 2024-08-06T11:09:42 Z nightfal Comparing Plants (IOI20_plants) C++17
19 / 100
 1153 ms 271016 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,q2;
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, temp2;
        temp1 = temp2 = 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 = temp2 = 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 'bool inRangeLeft(int, int, int)':
plants.cpp:88:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   88 | 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:89:58: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   89 | bool inRangeRight(int z, int y, int right) {return z < y && (right < z || y <= right) || y < z && (y <= right && right < z);}
      |                                                    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
plants.cpp: At global scope:
plants.cpp:17:16: warning: 'q2' defined but not used [-Wunused-variable]
   17 | static int l,m,q2;
      |                ^~

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 30 ms 4208 KB Output is correct
7 Correct 116 ms 27936 KB Output is correct
8 Correct 494 ms 269496 KB Output is correct
9 Correct 553 ms 269452 KB Output is correct
10 Correct 628 ms 269508 KB Output is correct
11 Correct 730 ms 269508 KB Output is correct
12 Correct 778 ms 269456 KB Output is correct
13 Correct 876 ms 269500 KB Output is correct
14 Correct 1010 ms 269376 KB Output is correct

Subtask #2
14.0 / 14.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 4 ms 1304 KB Output is correct
7 Correct 67 ms 10380 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 72 ms 10168 KB Output is correct
11 Correct 73 ms 10140 KB Output is correct
12 Correct 115 ms 10324 KB Output is correct
13 Correct 63 ms 10320 KB Output is correct

Subtask #3
0 / 13.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 4 ms 1304 KB Output is correct
7 Correct 67 ms 10380 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 72 ms 10168 KB Output is correct
11 Correct 73 ms 10140 KB Output is correct
12 Correct 115 ms 10324 KB Output is correct
13 Correct 63 ms 10320 KB Output is correct
14 Correct 132 ms 28112 KB Output is correct
15 Correct 918 ms 270260 KB Output is correct
16 Incorrect 126 ms 28068 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 77 ms 6740 KB Output is correct
4 Correct 1153 ms 271016 KB Output is correct
5 Incorrect 1109 ms 269764 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 344 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 15 ms 1792 KB Output is correct
8 Incorrect 10 ms 1544 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 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 750 ms 268768 KB Output is correct
7 Correct 888 ms 268964 KB Output is correct
8 Correct 901 ms 269216 KB Output is correct
9 Correct 889 ms 269248 KB Output is correct
10 Correct 676 ms 268720 KB Output is correct
11 Correct 782 ms 269528 KB Output is correct
12 Correct 770 ms 270528 KB Output is correct
13 Correct 822 ms 268740 KB Output is correct
14 Incorrect 830 ms 269016 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 30 ms 4208 KB Output is correct
7 Correct 116 ms 27936 KB Output is correct
8 Correct 494 ms 269496 KB Output is correct
9 Correct 553 ms 269452 KB Output is correct
10 Correct 628 ms 269508 KB Output is correct
11 Correct 730 ms 269508 KB Output is correct
12 Correct 778 ms 269456 KB Output is correct
13 Correct 876 ms 269500 KB Output is correct
14 Correct 1010 ms 269376 KB Output is correct
15 Correct 0 ms 348 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 1304 KB Output is correct
21 Correct 67 ms 10380 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 3 ms 1372 KB Output is correct
24 Correct 72 ms 10168 KB Output is correct
25 Correct 73 ms 10140 KB Output is correct
26 Correct 115 ms 10324 KB Output is correct
27 Correct 63 ms 10320 KB Output is correct
28 Correct 132 ms 28112 KB Output is correct
29 Correct 918 ms 270260 KB Output is correct
30 Incorrect 126 ms 28068 KB Output isn't correct
31 Halted 0 ms 0 KB -