oj.uz

Submission #1045625

# Submission time Handle Problem Language Result Execution time Memory
1045625 2024-08-06T06:32:55 Z nightfal Comparing Plants (IOI20_plants) C++17
19 / 100
 1076 ms 270872 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) {
    if (minI1>0) {
        auto[min2,minI2] = findMin(t,lz,1,0,m-1,std::max(0,minI1-k+1),minI1-1);
        if (min2==0) minI1 = 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) minI1 = minI2;
    }
    return minI1;
}
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,2*m);
    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: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: 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 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 32 ms 4428 KB Output is correct
7 Correct 116 ms 28108 KB Output is correct
8 Correct 485 ms 269508 KB Output is correct
9 Correct 570 ms 269504 KB Output is correct
10 Correct 638 ms 269272 KB Output is correct
11 Correct 778 ms 269404 KB Output is correct
12 Correct 800 ms 269504 KB Output is correct
13 Correct 892 ms 269516 KB Output is correct
14 Correct 1002 ms 269460 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 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 1212 KB Output is correct
7 Correct 66 ms 10164 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 4 ms 1372 KB Output is correct
10 Correct 70 ms 10268 KB Output is correct
11 Correct 73 ms 10068 KB Output is correct
12 Correct 116 ms 10420 KB Output is correct
13 Correct 62 ms 10320 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 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 1212 KB Output is correct
7 Correct 66 ms 10164 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 4 ms 1372 KB Output is correct
10 Correct 70 ms 10268 KB Output is correct
11 Correct 73 ms 10068 KB Output is correct
12 Correct 116 ms 10420 KB Output is correct
13 Correct 62 ms 10320 KB Output is correct
14 Correct 136 ms 28100 KB Output is correct
15 Correct 931 ms 270164 KB Output is correct
16 Incorrect 126 ms 28088 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 77 ms 6672 KB Output is correct
4 Correct 1076 ms 270872 KB Output is correct
5 Incorrect 1014 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 604 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 2 ms 604 KB Output is correct
7 Correct 10 ms 1544 KB Output is correct
8 Incorrect 12 ms 1528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 268748 KB Output is correct
7 Correct 800 ms 268996 KB Output is correct
8 Correct 778 ms 269160 KB Output is correct
9 Correct 904 ms 269348 KB Output is correct
10 Correct 655 ms 268736 KB Output is correct
11 Correct 720 ms 269308 KB Output is correct
12 Correct 745 ms 270528 KB Output is correct
13 Correct 777 ms 268992 KB Output is correct
14 Incorrect 793 ms 269028 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 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 32 ms 4428 KB Output is correct
7 Correct 116 ms 28108 KB Output is correct
8 Correct 485 ms 269508 KB Output is correct
9 Correct 570 ms 269504 KB Output is correct
10 Correct 638 ms 269272 KB Output is correct
11 Correct 778 ms 269404 KB Output is correct
12 Correct 800 ms 269504 KB Output is correct
13 Correct 892 ms 269516 KB Output is correct
14 Correct 1002 ms 269460 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 440 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 3 ms 1212 KB Output is correct
21 Correct 66 ms 10164 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 4 ms 1372 KB Output is correct
24 Correct 70 ms 10268 KB Output is correct
25 Correct 73 ms 10068 KB Output is correct
26 Correct 116 ms 10420 KB Output is correct
27 Correct 62 ms 10320 KB Output is correct
28 Correct 136 ms 28100 KB Output is correct
29 Correct 931 ms 270164 KB Output is correct
30 Incorrect 126 ms 28088 KB Output isn't correct
31 Halted 0 ms 0 KB -