oj.uz

Submission #422799

# Submission time Handle Problem Language Result Execution time Memory
422799 2021-06-10T12:35:36 Z 2fat2code Ancient Books (IOI17_books) C++17
0 / 100
 17 ms 23784 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;
pair<long long,long long>range[nmax];
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];
            }
            range[comp].fr = mini;
            range[comp].sc = maxi;
            ranges.push_back({mini, maxi});
        }
	}
	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 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 16 ms 23688 KB Output is correct
4 Correct 15 ms 23756 KB Output is correct
5 Incorrect 16 ms 23784 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 16 ms 23688 KB Output is correct
4 Correct 15 ms 23756 KB Output is correct
5 Incorrect 16 ms 23784 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 16 ms 23688 KB Output is correct
4 Correct 15 ms 23756 KB Output is correct
5 Incorrect 16 ms 23784 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 23756 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 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 16 ms 23688 KB Output is correct
4 Correct 15 ms 23756 KB Output is correct
5 Incorrect 16 ms 23784 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -