oj.uz

Submission #116928

# Submission time Handle Problem Language Result Execution time Memory
116928 2019-06-14T05:59:54 Z souhhcong Doktor (COCI17_doktor) C++14
90 / 100
 863 ms 68656 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define st first
#define nd second
const int N = 5e5+5;
int n, a[N];
int center[N];
int pref[N];
vector<pair<int,int>> seg[2*N];
int mx = -N;
pair<int,int> ans;
int cnt = 0;
map<pair<int,int>,int> check;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] == i)
            cnt++;
        pref[i] = cnt;
        center[i] = a[i]+i;
        if (a[i] < i)
            seg[center[i]].push_back({a[i],i});
        else
            seg[center[i]].push_back({i,a[i]});
    }
    for (int i = 1; i <= 2*n; i++)
    {
        if (seg[i].size() == 0) continue;
        int tmp = 0;
        tmp++;
        if (!check[{seg[i][0].st,seg[i][0].nd}])
        {
            tmp -= (pref[seg[i][0].nd] - pref[seg[i][0].st-1]);
            check[{seg[i][0].st,seg[i][0].nd}] = 1;
        }
        if (tmp > mx)
        {
            mx = tmp;
            ans = seg[i][0];
        }

        sort(seg[i].begin(),seg[i].end(), greater<pair<int,int> >() );
        for (int j = 1; j < seg[i].size(); j++)
        {
            int l = seg[i][j-1].st, r = seg[i][j-1].nd, L = seg[i][j].st, R = seg[i][j].nd;
            tmp++;
            if (!check[{L,R}])
            {
                tmp -= (pref[l-1] - pref[L-1] + pref[R] - pref[r]);
                check[{L,R}] = 1;
            }
            if (tmp > mx)
            {
                mx = tmp;
                ans = seg[i][j];
            }
        }

    }
    cout << a[ans.st] << ' ' << a[ans.nd];

}

Compilation message

doktor.cpp: In function 'int main()':
doktor.cpp:51:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < seg[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 23 ms 23908 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24004 KB Output is correct
2 Correct 22 ms 24024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24224 KB Output is correct
2 Correct 25 ms 24056 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24056 KB Output is correct
2 Correct 22 ms 23936 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24696 KB Output is correct
2 Correct 257 ms 39236 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 32228 KB Output is correct
2 Correct 93 ms 29040 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 68656 KB Output is correct
2 Correct 426 ms 49548 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 432 ms 50132 KB Output isn't correct
2 Halted 0 ms 0 KB -