Submission #3008604


Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

bool comp(pair<int, int> in1, pair<int, int> in2)
{
    if(in1.second < in2.second){
        return true;
    } else {
        return false;
    }
}

int main() {
    //cout.precision(10);
    int n, m;
    cin >> n >> m;
    int a[100100];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<pair<int, int> > c, b;
    for(int i = 1; i <= n - 1; i++){
        pair<int, int> in;
        in.first = a[i];
        if(a[i] > a[i + 1]){
            in.second = a[i + 1] + m;
        } else {
            in.second = a[i + 1];
        }
        b.push_back(in);
        c.push_back(in);
    }
    sort(b.begin(), b.end());
    sort(c.begin(), c.end(), comp);
    /*for(int i = 0; i < n - 1; i++){
        cout << b[i].first << " " << b[i].second << endl;
    }
    for(int i = 0; i < n - 1; i++){
        cout << c[i].first << " " << c[i].second << endl;
    }*/
    int minus[100100];
    for(int i = 0; i <= n; i++){
        minus[i] = 0;
    }
    int contain = 0;
    for(int i = 0; i < n - 1; i++){
        if((b[i].first <= (m + 1 - 2)) && (b[i].second >= (m + 1))){
            contain++;
            minus[1] += m - b[i].first;
        }
    }
    //cout << minus[1] << endl;
    for(int i = 2; i <= m; i++){
        int ok = n - 2;
        int ng = -1;
        while(ok - ng > 1){
            int mid = (ok + ng) / 2;
            if(b[mid].first >= (i - 2)){
                ok = mid;
            } else {
                ng = mid;
            }
        }
        while(b[ok].first == (i - 2)){
            contain++;
            ok++;
        }
        ok = n - 2;
        ng = -1;
        while(ok - ng > 1){
            int mid = (ok + ng) / 2;
            if(c[mid].second >= (i - 1)){
                ok = mid;
            } else {
                ng = mid;
            }
        }
        while(c[ok].second == (i - 1)){
            contain--;
            minus[i] -= (c[ok].second - c[ok].first - 1);
            ok++;
        }
        ok = n - 2;
        ng = -1;
        while(ok - ng > 1){
            int mid = (ok + ng) / 2;
            if(c[mid].second >= (i - 1 + m)){
                ok = mid;
            } else {
                ng = mid;
            }
        }
        while(c[ok].second == (i - 1 + m)){
            contain--;
            minus[i] -= (c[ok].second - c[ok].first - 1);
            ok++;
        }
        minus[i] += minus[i - 1] + contain;
        //cout << i << " " << contain << " " << minus[i] << endl;
    }
    int sum = 0;
    for(int i = 0; i < n - 1; i++){
        sum += b[i].second - b[i].first;
    }
    int minimum = minus[1];
    for(int i = 2; i <= m; i++){
        minimum = max(minimum, minus[i]);
    }
    cout << sum - minimum << endl;
    /*for(int i = 1; i <= m; i++){
        cout << minus[i] << endl;
    }*/
    return 0;
}

Submission Info

Submission Time
Task E - Snuke Line
User kort0n
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3329 Byte
Status RE
Exec Time 147 ms
Memory 1024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
WA × 2
WA × 12
RE × 27
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt
Case Name Status Exec Time Memory
00_example_01.txt WA 1 ms 256 KB
00_example_02.txt WA 1 ms 256 KB
01.txt WA 1 ms 256 KB
02.txt WA 2 ms 384 KB
03.txt WA 1 ms 256 KB
04.txt WA 1 ms 256 KB
05.txt RE 96 ms 256 KB
06.txt WA 1 ms 256 KB
07.txt WA 1 ms 256 KB
08.txt WA 1 ms 256 KB
09.txt WA 1 ms 256 KB
10.txt RE 96 ms 256 KB
11.txt RE 139 ms 1024 KB
12.txt RE 140 ms 1024 KB
13.txt RE 136 ms 1024 KB
14.txt RE 137 ms 1024 KB
15.txt RE 138 ms 1024 KB
16.txt RE 144 ms 1024 KB
17.txt RE 141 ms 1024 KB
18.txt RE 138 ms 1024 KB
19.txt RE 141 ms 1024 KB
20.txt RE 140 ms 1024 KB
21.txt RE 142 ms 1024 KB
22.txt RE 140 ms 1024 KB
23.txt RE 140 ms 1024 KB
24.txt RE 140 ms 1024 KB
25.txt RE 141 ms 1024 KB
26.txt RE 140 ms 1024 KB
27.txt RE 142 ms 1024 KB
28.txt RE 143 ms 1024 KB
29.txt RE 145 ms 1024 KB
30.txt RE 147 ms 1024 KB
31.txt RE 142 ms 1024 KB
32.txt RE 143 ms 1024 KB
33.txt RE 138 ms 1024 KB
34.txt RE 141 ms 1024 KB
35.txt RE 141 ms 1024 KB
36.txt WA 1 ms 256 KB
37.txt WA 2 ms 640 KB