oj.uz

Submission #276532

# Submission time Handle Problem Language Result Execution time Memory
276532 2020-08-20T13:31:49 Z sjimed Circus (Balkan15_CIRCUS) C++14
49 / 100
 4000 ms 18808 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];
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);
    
    sort(all(p));
    p.erase(unique(all(p)), p.end());

    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 && x+1 < p.size()) pQ.em(p[x+1] - p[par], mp(x+1, par));
        else if(x <= par && x-1 >= 0) pQ.em(p[par] - p[x-1], mp(x-1, par));

        if(chk[x]) continue;
        chk[x] = true;
        dp[x] = cost;        

        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:46:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(x >= par && x+1 < p.size()) pQ.em(p[x+1] - p[par], mp(x+1, par));
      |                        ~~~~^~~~~~~~~~
circus.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(k < p.size()) pQ.em(p[k] - p[x], mp(k, x));
      |            ~~^~~~~~~~~~
circus.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     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 4080 ms 5096 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 1 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 1 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 549 ms 504 KB Output is correct
6 Correct 527 ms 504 KB Output is correct
7 Correct 511 ms 504 KB Output is correct
8 Correct 510 ms 504 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 1 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 549 ms 504 KB Output is correct
6 Correct 527 ms 504 KB Output is correct
7 Correct 511 ms 504 KB Output is correct
8 Correct 510 ms 504 KB Output is correct
9 Correct 968 ms 8620 KB Output is correct
10 Correct 1033 ms 11000 KB Output is correct
11 Correct 1018 ms 10232 KB Output is correct
12 Correct 975 ms 18808 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4080 ms 5096 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 4080 ms 5096 KB Time limit exceeded
2 Halted 0 ms 0 KB -