oj.uz

Submission #276556

# Submission time Handle Problem Language Result Execution time Memory
276556 2020-08-20T13:46:50 Z sjimed Circus (Balkan15_CIRCUS) C++14
49 / 100
 4000 ms 9336 KB 
#include "circus.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,pii> piii;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
int dp[100010];
bool chk[100010];
set<int> s;
vector<int> p, v1, v2;
priority_queue<piii, vector<piii>, greater<piii>> pQ;
vector<int> ans;

void init(int N, int M, int P[]){
    n = N;
    m = M;

    for(int i=0; i<n; i++) p.eb(P[i]);

    p.eb(m);
    s.insert(m);
    
    sort(all(p));
    p.erase(unique(all(p)), p.end());

    for(int i=0; i<p.size(); i++) s.insert(i);
    s.insert(-1);
    s.insert(p.size());

    pQ.em(0, mp(p.size()-1, p.size()-1));

    while(pQ.size()) {
        int cost = pQ.top().fi;
        int x = pQ.top().se.fi;
        int par = pQ.top().se.se;
        pQ.pop();

        if(x > par) {
            auto y = *s.upper_bound(x);
            if(y < p.size()) pQ.em(p[y] - p[par], mp(y, par));
            //if(x+1 < p.size()) pQ.em(p[x+1] - p[par], mp(x+1, par));
        } 
        else {
            auto y = *prev(s.lower_bound(x));
            if(y >= 0) pQ.em(p[par] - p[y], mp(y, par));
            //if(x-1 >= 0) pQ.em(p[par] - p[x-1], mp(x-1, par));
        }

        if(chk[x]) continue;
        chk[x] = true;
        dp[x] = cost;
        //s.erase(x);

        int k = lower_bound(all(p), p[x] + cost) - p.begin();
        if(k < p.size()) pQ.em(p[k] - p[x], mp(k, x));

        k = upper_bound(all(p), p[x] - cost) - p.begin() - 1;
        if(k >= 0) pQ.em(p[x] - p[k], mp(k, x));
    }

    for(int i=0; i<p.size(); i++) {
        if(v1.empty() || v1.back() < p[i] - dp[i]) v1.eb(p[i] - dp[i]);
        else v1.eb(v1.back());
    }

    for(int i=p.size()-1; i>=0; i--) {
        if(v2.empty() || v2.back() > p[i] + dp[i]) v2.eb(p[i] + dp[i]);
        else v2.eb(v2.back());
    }

    reverse(all(v2));
}

int minLength(int D) {
    int ret = m - D;

    int k = lower_bound(all(v1), D) - v1.begin();
    ret = min(ret, p[k] - D);

    k = upper_bound(all(v2), D) - v2.begin() - 1;
    if(k >= 0) ret = min(ret, D - p[k]);

    return ret;
}

Compilation message

circus.cpp: In function 'void init(int, int, int*)':
circus.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0; i<p.size(); i++) s.insert(i);
      |                  ~^~~~~~~~~
circus.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             if(y < p.size()) pQ.em(p[y] - p[par], mp(y, par));
      |                ~~^~~~~~~~~~
circus.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if(k < p.size()) pQ.em(p[k] - p[x], mp(k, x));
      |            ~~^~~~~~~~~~
circus.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0; i<p.size(); i++) {
      |                  ~^~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
   14 |  long long max_code;
      |            ^~~~~~~~
grader.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |   scanf("%d", &P[i]);
      |   ~~~~~^~~~~~~~~~~~~
grader.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   scanf("%d", &d);
      |   ~~~~~^~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 7908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 868 ms 632 KB Output is correct
6 Correct 878 ms 632 KB Output is correct
7 Correct 932 ms 592 KB Output is correct
8 Correct 950 ms 600 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 868 ms 632 KB Output is correct
6 Correct 878 ms 632 KB Output is correct
7 Correct 932 ms 592 KB Output is correct
8 Correct 950 ms 600 KB Output is correct
9 Correct 1440 ms 8524 KB Output is correct
10 Correct 1394 ms 5068 KB Output is correct
11 Correct 1372 ms 4600 KB Output is correct
12 Correct 1384 ms 9336 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 7908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 7908 KB Time limit exceeded
2 Halted 0 ms 0 KB -