oj.uz

Submission #598799

# Submission time Handle Problem Language Result Execution time Memory
598799 2022-07-19T05:44:10 Z 박상훈(#8456) Potemkin cycle (CEOI15_indcyc) C++17
0 / 100
 11 ms 5376 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[200200];
vector<pair<int, int>> query[200200];
ll ans[200200];

ll calc(pair<int, int> A, pair<int, int> B, int x){
    ll a2 = B.first - A.first;
    ll a1 = A.second - B.second;
    return a2 * x * x + a1 * x;
}

int ccw(pair<int, int> A, pair<int, int> B, pair<int, int> C){
    ll ret = (ll)(B.first-A.first) * (C.second-A.second) - (ll)(B.second-A.second) * (C.first-A.first);
    if (ret>0) return 1;
    if (ret<0) return -1;
    return 0;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=m;i++) scanf("%d", a+i);

    int q;
    scanf("%d", &q);
    for (int i=1;i<=q;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        query[y].emplace_back(x, i);
    }

    vector<pair<int, int>> hull;
    vector<ll> best;
    vector<ll> prf;
    for (int i=1;i<=m;i++){
        ///hull modify
        pair<int, int> P = {i, a[i]};
        while(hull.size()>=2){
            auto s = hull.back(); hull.pop_back();
            auto f = hull.back();
            if (ccw(f, s, P)==1) {hull.push_back(s); break;}

            best.pop_back();
            prf.pop_back();
        }

        if (hull.empty()){
            hull.push_back(P);
            prf.push_back(0);
        }
        else{
            int x = (a[i]-hull.back().second) / ((i-hull.back().first)*2);
            x = max(x, 1);
            if (calc(hull.back(), P, x) > calc(hull.back(), P, x+1)) x = x+1;
            best.push_back(x);
            prf.push_back(prf.back() + calc(hull.back(), P, x));
            hull.push_back(P);
        }

        /*printf("\nx = %d\n", i);
        printf("hull: ");
        for (auto &[x, y]:hull) printf("(%d, %d) ", x, y);
        printf("\nbest: ");
        for (auto &x:best) printf("%d ", x);
        printf("\nprf: ");
        for (auto &x:prf) printf("%lld ", x);
        printf("\n");*/

        ///
        for (auto &[y, idx]:query[i]){
            int pos = lower_bound(best.begin(), best.end(), y) - best.begin();
            ans[idx] = prf[pos] +  (-a[1] + (hull[0].first-1));

            ans[idx] += (ll)y*hull[pos].second + (ll)(i-hull[pos].first)*y*y;
        }
    }

    for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
    return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:25:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     for (int i=1;i<=m;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~
indcyc.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
indcyc.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Integer 12 violates the range [1, 4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Integer 11 violates the range [1, 10]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Integer 16 violates the range [1, 10]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Integer 593 violates the range [1, 100]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Integer 7117 violates the range [1, 100]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4948 KB Integer 3185 violates the range [1, 300]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5204 KB Integer 553800 violates the range [1, 1000]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5076 KB Integer 442270 violates the range [1, 1000]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5376 KB Integer 14959 violates the range [1, 440]
2 Halted 0 ms 0 KB -