답안 #382615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382615	2021-03-27T22:11:00 Z	gmyu	Pyramid Base (IOI08_pyramid_base)	C++14	27 / 100	1280 ms	118968 KB

pyramid_base

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI08_pyramid_base
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()
#define adjread {int a, b; cin >> a >> b; adjlist[a].pb(b); adjlist[b].pb(a); }

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y, ypar;
    int type;
    int c;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
vector<NODE> p0, p;
vi ylist;
map<int, int> y2i;
int i2y[MAXV*2];

bool debug;

int M, N, B, ctP;

/// ------ Segment Treee --------
int Nseg[2];
struct SEGNODE {
    ll mi;                 /// mx is always updated before lazy value is used.
    int lzVal;
    bool LazyPushedDown;    /// flag whether we already pushed down the lazy additional value
};
SEGNODE seg[1<<19];    /// max 2e5 unique y, which needs 2^19 for Nseg

void pullUp(int v, int l, int m, int r) {
    if(l==r) return;

    seg[v].mi  = min(seg[2*v].mi, seg[2*v+1].mi);

}
void pushDown(int v, int l, int m, int r) {

    if(l==r) {
        seg[v].LazyPushedDown = true;
        return;
    }

    if(seg[v].LazyPushedDown) return;

    /// push down
    int u = 2*v;
    seg[u].mi += seg[v].lzVal;
    seg[u].lzVal += seg[v].lzVal;
    seg[u].LazyPushedDown = false;
    if(debug) cout << " .. .. push down  to " << l << "," << m << " = " << seg[u].mi << " at node " << u << endl;

    u = 2*v + 1;
    seg[u].mi += seg[v].lzVal;
    seg[u].lzVal += seg[v].lzVal;
    seg[u].LazyPushedDown = false;
    if(debug) cout << " .. .. push down  to " << m+1 << "," << r << " = " << seg[u].mi << " at node " << u  << endl;

    /// update v
    seg[v].lzVal = 0;
    seg[v].LazyPushedDown = true;

}
void buildSeg(int v = 1, int l = Nseg[0], int r = Nseg[1]) {
    //if(debug) cout << l << " " << r << endl;

    if(l == r) { // leaf
        seg[v].mi = 0;
        seg[v].lzVal = 0; seg[v].LazyPushedDown = true;
        return;
    }

    int mid = (l + r) / 2;
    buildSeg(2*v, l, mid); buildSeg(2*v+1, mid+1, r);
    seg[v].mi = 0;
    seg[v].lzVal = 0; seg[v].LazyPushedDown = true;
}
void initSeg() {
    /// build a segment tree for array of interest indexed from Nseg[0] to Nseg[1]
    Nseg[0] = 0;
    Nseg[1] = sz(ylist)-1;
    buildSeg();
}
void updateSeg(int ule, int uri, int val, int v = 1, int l = Nseg[0], int r = Nseg[1]){
    if(l > r) return;
    if(r < ule || l > uri) return;
    if(l == r) {
        seg[v].mi += val;
        seg[v].LazyPushedDown = true;
        if(debug) cout << " .. .. seg " << l << "," << r << " = " << seg[v].mi << endl;
        return;
    }

    int mid = (l + r) / 2;
    if(ule <= l && r <= uri) {
        pushDown(v, l, mid, r);

        seg[v].mi += val;
        seg[v].lzVal += val;
        seg[v].LazyPushedDown = false;
        if(debug) cout << " .. .. seg " << l << "," << r << " = " << seg[v].mi << endl;

        return;
    }

    pushDown(v, l, mid, r);

    updateSeg(ule, uri, val, 2*v, l, mid);
    updateSeg(ule, uri, val, 2*v+1, mid+1, r);

    pullUp(v, l, mid, r);
    if(debug) cout << " .. .. seg " << l << "," << r << " = " << seg[v].mi << endl;
}
int querySeg(int qle, int qri, int v = 1, int l = Nseg[0], int r = Nseg[1]) {
    if(r < qle || l > qri) return MOD;
    if(qle <= l && r <= qri) {
        return seg[v].mi;
    }

    int mid = (l + r) / 2;
    pushDown(v, l, mid, r);
    int rect = min(querySeg(qle, qri, 2*v, l, mid), querySeg(qle, qri, 2*v+1, mid+1, r));
    pullUp(v, l, mid, r);
    return rect;
}

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    int i, j, k;

    cin >> M >> N >> B >> ctP;

    for(i=0;i<ctP;i++) {
        int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c;
        if(x1>x2) swap(x1,x2);
        if(y1>y2) swap(y1, y2);
        x2++; //y2++;
        p0.pb((NODE){x1, y1, y2, 0, c});
        p0.pb((NODE){x2, y2, y1, 1, c});
    }

    int ans = 0, lo, hi;
    lo = 0; hi = min(M, N);

    while(lo <= hi) {
        int mid = (lo+hi)/2;
        if(debug) cout << endl << "working on size = " << mid << endl;

        /// expand each rect to left/bottom by box size
        p.clear(); ylist.clear();
        for(NODE v : p0) {
            if(v.type == 0) {
                v.x = max(1, v.x - mid + 1);
                v.y = max(1, v.y - mid + 1);
            } else {
                v.ypar = max(1, v.ypar - mid +1);
            }
            p.pb(v);
            ylist.pb(v.y); ylist.pb(v.ypar);
        }

        /// compress y
        sort(p.begin(), p.end());
        sort(ylist.begin(), ylist.end());
        ylist.erase(unique(ylist.begin(), ylist.end()), ylist.end());
        for(i=0;i<sz(ylist);i++) {
            y2i[ylist[i]] = i; i2y[i] = ylist[i];
            if(debug) cout << ylist[i] << " ";
            if(debug && i == sz(ylist)-1) cout << endl;
        }

        /// init seg
        initSeg();

        /// cal
        bool ok = false;
        i = sz(p) -1;
        if( (M - p[i].x+1) >= mid && N >= mid ) {
            ok = true;
        } else {
            auto it = upper_bound(ylist.begin(), ylist.end(), N-mid+1);
            int r1 = (it - ylist.begin()) -1;
            r1 = max(0, r1);
            if(debug) cout << " .. query range to " << r1 << endl;

            int pre_x = p[0].x;
            for(i =0; i<sz(p); i++) {
                NODE v = p[i];

                if(v.x + mid > M) { break;}

                if(i >0 && v.x != p[i-1].x) {
                    int b0 = querySeg(0, r1);
                    if(b0 <= B) {
                        ok = true;
                        if(debug) cout <<" at " << v.x << " size " << mid << " ok" << endl;
                        break;   /// can make a rect with size of mid
                    }
                    pre_x = v.x;
                }

                if(debug) cout << "work on " << v.x << ", " << v.y << " for " << v.c << endl;
                if(v.type==0) {
                    j = y2i[v.y]; k = y2i[v.ypar];
                    updateSeg(j, k, v.c);
                    if(debug) cout << " .. update range " << v.y << ", " << v.ypar << " add cost of " << v.c << " and min= " << querySeg(0, r1) << endl;
                } else {
                    j = y2i[v.ypar]; k = y2i[v.y];
                    updateSeg(j, k, -v.c);
                    if(debug) cout << " .. erase range " << v.ypar << ", " << v.y << " and min cost = " << querySeg(0, r1) << endl;
                }
            }
        }

        /// next step
        if(ok) {
            ans = max(ans, mid);
            lo=mid+1;
            if(debug) cout << "-> size = " << ans << " OK. next " << lo << "," << hi << endl;
        } else {
            hi = mid -1;
            if(debug) cout << "-> size = " << ans << " NOK. next " << lo << "," << hi << endl;
        }

    }

    if(debug) cout << endl << "EOL" << endl;
    cout << ans << endl;

}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:222:17: warning: variable 'pre_x' set but not used [-Wunused-but-set-variable]
  222 |             int pre_x = p[0].x;
      |                 ^~~~~

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	364 KB	Output isn't correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	364 KB	Output is correct

Subtask #3

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	492 KB	Output is correct

Subtask #4

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	748 KB	Output is correct

Subtask #5

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	1144 KB	Output is correct

Subtask #6

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	15 ms	620 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	47 ms	1400 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	1576 KB	Output is correct
2	Correct	164 ms	1704 KB	Output is correct
3	Correct	121 ms	1752 KB	Output is correct

Subtask #9

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	573 ms	6600 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	803 ms	10960 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1280 ms	16716 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #12

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1222 ms	14132 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #13

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	301 ms	67128 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #14

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	432 ms	100064 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #15

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	555 ms	118968 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-