oj.uz

Submission #801577

# Submission time Handle Problem Language Result Execution time Memory
801577 2023-08-02T06:44:29 Z 반딧불(#10089) Cultivation (JOI17_cultivation) C++17
5 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 2e9;

ll n, m; int k;
ll X[302], Y[302];
int rx[302], ry[302], sx, sy;
ll ans = LLONG_MAX;

struct Event{
    ll x, y, v;
    Event(){}
    Event(ll x, ll y, ll v): x(x), y(y), v(v){}
    bool operator<(const Event &r)const{
        if(x!=r.x) return x<r.x;
        return v > r.v;
    }
} vec[1002];

struct Interval{
    ll l, r; /// ���� ����
    ll ldist, rdist, mdist; /// �ּ� ����
    Interval(){}
    Interval(ll l, ll r, ll ldist, ll rdist, ll mdist): l(l), r(r), ldist(ldist), rdist(rdist), mdist(mdist){}
    bool operator<(const Interval &nxt)const{
        return l<nxt.l;
    }
};

vector<ll> vx, vy;
struct diffTree{
    int cnt[1024];
    ll lv[1024], rv[1024], diff[1024];

    inline void merge(int i){
        cnt[i] = cnt[i*2] + cnt[i*2+1];
        lv[i] = min(lv[i*2], lv[i*2+1]);
        rv[i] = max(rv[i*2], rv[i*2+1]);
        diff[i] = max({diff[i*2], diff[i*2+1], (cnt[i*2] && cnt[i*2+1]) ? (lv[i*2+1] - rv[i*2] - 1) : 0});
    }

    void init(int i, int l, int r){
        if(l==r){
            cnt[i] = 0;
            lv[i] = INF, rv[i] = 0, diff[i] = 0;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        merge(i);
    }

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            cnt[i] += v;
            if(!cnt[i]) lv[i] = INF, rv[i] = 0, diff[i] = 0;
            else lv[i] = rv[i] = vy[l-1], diff[i] = 0;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        merge(i);
    }
} difftree;

void renumber(){
    vx = vector<ll> (X+1, X+k+1);
    vy = vector<ll> (Y+1, Y+k+1);
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    sx = (int)vx.size(), sy = (int)vy.size();
    for(int i=1; i<=k; i++){
        rx[i] = lower_bound(vx.begin(), vx.end(), X[i]) - vx.begin() + 1;
        ry[i] = lower_bound(vy.begin(), vy.end(), Y[i]) - vy.begin() + 1;
    }
}

pair<ll, int> dqL[1002], dqR[1002], dqLen[1002];
int l1, l2, r1, r2, len1, len2;

Interval info[1002];
int infoCnt;

int main(){
    scanf("%lld %lld %d", &n, &m, &k);
//    n=m=1000000000, k=300;
    for(int i=1; i<=k; i++){
        scanf("%lld %lld", &X[i], &Y[i]);
//        X[i] = Y[i] = i*i+i+2;
    }
    renumber();

    vector<ll> udlength (1, n-1); /// ����Ǵ� ������
    for(int i=1; i<=k; i++){
        udlength.push_back(X[i] - 1);
        udlength.push_back(n - X[i]);
        for(int j=1; j<=k; j++){
            if(X[i] < X[j]) udlength.push_back(X[j] - X[i] - 1);
            udlength.push_back(X[i] + n - X[j] - 1);
        }
    }
    sort(udlength.begin(), udlength.end());
    udlength.erase(unique(udlength.begin(), udlength.end()), udlength.end());

    for(ll ud: udlength){ /// �� - �Ʒ� ����
        if(ud<0) continue;

        for(int i=1; i<=k; i++){
            vec[i*2-2] = Event(X[i], ry[i], 1);
            vec[i*2-1] = Event(X[i]+ud+1, ry[i], -1);
        }
        sort(vec, vec+k+k);

        infoCnt = 0;
        difftree.init(1, 1, sy);
        bool bad = 0;

        for(int s=0; s<k+k; s++){
            int e = s;
            while(e+1 < k+k && vec[e+1].x == vec[s].x) e++;
            if(e+1 == k+k) break;

            /// [s, e] ���� �������� ó��
            for(int i=s; i<=e; i++){
                if(vec[i].v == 1) difftree.update(1, 1, sy, vec[i].y, 1);
                else difftree.update(1, 1, sy, vec[i].y, -1);
            }

            /// ��� ������ �Ѿ
            if(difftree.cnt[1] == 0){
                bad = 1;
                break;
            }

            info[infoCnt++] = Interval(vec[s].x, vec[e+1].x-1, difftree.lv[1] - 1, m - difftree.rv[1], difftree.diff[1]);
            s = e;
        }
        if(bad || !infoCnt) continue;

        int j = 0;
        l1 = l2 = r1 = r2 = len1 = len2 = 0;
        dqL[l2++] = make_pair(info[0].ldist, 0);
        dqR[r2++] = make_pair(info[0].rdist, 0);
        dqLen[len2++] = make_pair(info[0].mdist, 0);

        for(int i=0; i<infoCnt; i++){
            if(l1!=l2 && dqL[l1].second < i) l1++;
            if(r1!=r2 && dqR[r1].second < i) r2++;
            if(len1!=len2 && dqLen[len1].second < i) len1++;
            while(j < infoCnt && info[j].r - info[i].l + 1 < n){
                j++;
                while(l1!=l2 && dqL[l2-1].first <= info[j].ldist) l2--;
                dqL[l2++] = make_pair(info[j].ldist, j);
                while(r1!=r2 && dqR[r2-1].first <= info[j].rdist) r2--;
                dqR[r2++] = make_pair(info[j].rdist, j);
                while(len1!=len2 && dqLen[len2-1].first <= info[j].mdist) len2--;
                dqLen[len2++] = make_pair(info[j].mdist, j);
            }
            if(j == infoCnt) break;
            ll minL = dqL[l1].first, minR = dqR[r1].first, len = dqLen[len1].first;
            ans = min(ans, ud + max(len, minL+minR));
        }
    }

    printf("%lld", ans);
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%lld %lld %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%lld %lld", &X[i], &Y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Incorrect 0 ms 340 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Incorrect 0 ms 340 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Incorrect 0 ms 340 KB Output isn't correct
18 Halted 0 ms 0 KB -