oj.uz

Submission #422809

# Submission time Handle Problem Language Result Execution time Memory
422809 2021-06-10T12:41:45 Z 2fat2code Ancient Books (IOI17_books) C++17
0 / 100
 18 ms 23788 KB 
#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 1000005;

long long n, ans = 0, viz[nmax], comp = 0, cost;
vector<pair<long long,long long>>ranges;
vector<long long>nod[nmax];

long long minimum_walk(vector<int> p, int s) {
	n = (int)p.size();
	for(int i=0;i<n;i++){
        ans += abs(p[i] - i);
	}
	for(int i=0;i<n;i++){
        if(!viz[i]){
            int maxi = i, mini = i;
            comp++;
            viz[i] = comp;
            int curr = p[i];
            while(curr != i){
                viz[curr] = comp;
                maxi = max(maxi, curr);
                mini = min(mini, curr);
                curr = p[curr];
            }
            ranges.push_back({mini, maxi});
        }
	}
    while(ranges.size() && ranges.back().fr == ranges.back().sc){
        ranges.pop_back();
    }
    reverse(all(ranges));
    while(ranges.size() && ranges.back().fr == ranges.back().sc){
        ranges.pop_back();
    }
	sort(all(ranges));
	deque<pair<int,int>>Q;
	for(auto it : ranges){
        Q.push_back(it);
	}
	queue<pair<long long, long long>>rn;
	while(Q.size()){
        cost += 2;
        rn.push(Q.front());
        Q.pop_front();
        while(rn.size()){
            auto it = rn.front();
            rn.pop();
            while(Q.size() && Q.front().fr <= it.sc){
                rn.push(Q.front());
                Q.pop_front();
            }
        }
	}
	cost -= 2LL;
	return ans + cost;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23728 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23728 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23728 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 23788 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23728 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -