Submission #65165

#	Time	Username	Problem	Language	Result	Execution time	Memory
65165		wleung_bvg	New Home (APIO18_new_home)	C++14	100 / 100	2962 ms	973848 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define D_INF numeric_limits<double>::infinity()
#define MIN(a, b) ((a) = min((a), (b)))
#define MAX(a, b) ((a) = max((a), (b)))
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(), (a).end()
#define For(i, a, b) for (auto i = (a); i < (b); i++)
#define FOR(i, b) For(i, 0, b)
#define Rev(i, a, b) for (auto i = (a); i > (b); i--)
#define REV(i, a) Rev(i, a, -1)
#define sz(a) ((int) (a).size())
#define nl '\n'
#define sp ' '
#define uint unsigned int
#define ull unsigned long long
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pill pair<int, ll>
#define plli pair<ll, int>
#define pdd pair<double, double>
#define uset unordered_set
#define umap unordered_map
#define pq priority_queue
template<typename T> using minpq = pq<T, vector<T>, greater<T>>;
template<typename T> using maxpq = pq<T, vector<T>, less<T>>;
template<typename T1,typename T2,typename H1=hash<T1>,typename H2=hash<T2>>struct pair_hash{size_t operator()(const pair<T1,T2>&p)const{return 31*H1{}(p.first)+H2{}(p.second);}};

#define _bufferSize 4096
#define _maxNumLength 128
char _inputBuffer[_bufferSize+1],*_inputPtr=_inputBuffer,_outputBuffer[_bufferSize],_c,_sign,*_tempInputBuf=nullptr,_numBuf[_maxNumLength],_tempOutputBuf[_maxNumLength],_fill=' ';
const char*_delimiter=" ";int _cur,_outputPtr=0,_numPtr=0,_precision=6,_width=0,_tempOutputPtr=0,_cnt;ull _precisionBase=1000000;
#define _peekchar() (*_inputPtr?*_inputPtr:(_inputBuffer[fread(_inputPtr=_inputBuffer,1,_bufferSize,stdin)]='\0',*_inputPtr))
#define _getchar() (*_inputPtr?*_inputPtr++:(_inputBuffer[fread(_inputPtr=_inputBuffer,1,_bufferSize,stdin)]='\0',*_inputPtr++))
#define _hasNext() (*_inputPtr||!feof(stdin))
#define _readSignAndNum(x) do{(x)=_getchar();}while((x)<=' ');_sign=(x)=='-';if(_sign)(x)=_getchar();for((x)-='0';(_c=_getchar())>='0';(x)=(x)*10+_c-'0')
#define _readFloatingPoint(x,T) for(T _div=1.0;(_c=_getchar())>='0';(x)+=(_c-'0')/(_div*=10))
#define rc(x) do{do{(x)=_getchar();}while((x)<=' ');}while(0)
#define ri(x) do{_readSignAndNum(x);if(_sign)(x)=-(x);}while(0)
#define rd(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,double);if(_sign)(x)=-(x);}while(0)
#define rld(x) do{_readSignAndNum(x);if(_c=='.')_readFloatingPoint(x,ld);if(_sign)(x)=-(x);}while(0)
#define rcs(x) do{_cur=0;do{_c=_getchar();}while(_c<=' ');do{(x)[_cur++]=_c;}while((_c=_getchar())>' ');(x)[_cur]='\0';}while(0)
#define rs(x) do{if(!_tempInputBuf)assert(0);rcs(_tempInputBuf);(x)=string(_tempInputBuf,_cur);}while(0)
#define rcln(x) do{_cur=0;do{_c=_getchar();}while(_c<=' ');do{(x)[_cur++]=_c;}while((_c=_getchar())>=' ');(x)[_cur]='\0';}while(0)
#define rln(x) do{if(!_tempInputBuf)assert(0);rcln(_tempInputBuf);(x)=string(_tempInputBuf,_cur);}while(0)
#define setLength(x) do{if(_tempInputBuf)delete[](_tempInputBuf);_tempInputBuf=new char[(x)+1];}while(0)
void read(int&x){ri(x);}void read(uint&x){ri(x);}void read(ll&x){ri(x);}void read(ull&x){ri(x);}void read(double&x){rd(x);}void read(ld&x){rld(x);}
void read(char&x){rc(x);}void read(char*x){rcs(x);}void read(string&x){rs(x);}bool hasNext(){while(_hasNext()&&_peekchar()<=' ')_getchar();return _hasNext();}
template<typename T,typename...Ts>void read(T&&x,Ts&&...xs){read(x);read(forward<Ts>(xs)...);}
#define _flush() do{_flushBuf();fflush(stdout);}while(0)
#define _flushBuf() (fwrite(_outputBuffer,1,_outputPtr,stdout),_outputPtr=0)
#define _putchar(x) (_outputBuffer[_outputPtr==_bufferSize?_flushBuf():_outputPtr]=(x),_outputPtr++)
#define _writeTempBuf(x) (_tempOutputBuf[_tempOutputPtr++]=(x))
#define _writeOutput() for(int _i=0;_i<_tempOutputPtr;_putchar(_tempOutputBuf[_i++]));_tempOutputPtr=0
#define _writeNum(x,T,digits) _cnt=0;for(T _y=(x);_y;_y/=10,_cnt++)_numBuf[_numPtr++]='0'+_y%10;for(;_cnt<digits;_cnt++)_numBuf[_numPtr++]='0';_flushNumBuf();
#define _writeFloatingPoint(x,T) ull _I=(ull)(x);ull _F=((x)-_I)*_precisionBase+(T)(0.5);if(_F>=_precisionBase){_I++;_F=0;}_writeNum(_I,ull,1);_writeTempBuf('.');_writeNum(_F,ull,_precision)
#define _checkFinite(x) if(std::isnan(x)){wcs("NaN");}else if(std::isinf(x)){wcs("Inf");}
#define _flushNumBuf() for(;_numPtr;_writeTempBuf(_numBuf[--_numPtr]))
#define _fillBuf(x) for(int _i=0;_i<(x);_i++)_putchar(_fill)
#define _flushTempBuf() int _tempLen=_tempOutputPtr;_fillBuf(_width-_tempLen);_writeOutput();_fillBuf(-_width-_tempLen)
#define wb(x) do{if(x)_writeTempBuf('1');else _writeTempBuf('0');_flushTempBuf();}while(0)
#define wc(x) do{_writeTempBuf(x); _flushTempBuf();}while(0)
#define wi(x) do{if((x)<0){_writeTempBuf('-');_writeNum(-(x),uint,1);}else{_writeNum(x,uint,1);}_flushTempBuf();}while(0)
#define wll(x) do{if((x)<0){_writeTempBuf('-');_writeNum(-(x),ull,1);}else{_writeNum(x,ull,1);}_flushTempBuf();}while(0)
#define wd(x) do{_checkFinite(x)else if((x)<0){_writeTempBuf('-');_writeFloatingPoint(-(x),double);}else{_writeFloatingPoint(x,double);}_flushTempBuf();}while(0)
#define wld(x) do{_checkFinite(x)else if((x)<0){_writeTempBuf('-');_writeFloatingPoint(-(x),ld);}else{_writeFloatingPoint(x,ld);}_flushTempBuf();}while(0)
#define wcs(x) do{int _slen=strlen(x);_fillBuf(_width-_slen);for(const char*_p=(x);*_p;_putchar(*_p++));_fillBuf(-_width-_slen);}while(0)
#define ws(x) do{_fillBuf(_width-(int)(x).length());for(int _i=0;_i<(int)(x).length();_putchar(x[_i++]));_fillBuf(-_width-(int)(x).length());}while(0)
#define setPrecision(x) do{_precision=(x);_precisionBase=1;for(int _i=0;_i<(x);_i++,_precisionBase*=10);}while(0)
#define setDelimiter(x) do{_delimiter=(x);}while(0)
#define setWidth(x) do{_width=(x);}while(0)
#define setFill(x) do{_fill=(x);}while(0)
void write(bool x){wb(x);}void write(int x){wi(x);}void write(uint x){wi(x);}void write(ll x){wll(x);}void write(ull x){wll(x);}void write(double x){wd(x);}void write(ld x){wld(x);}
void write(char x){wc(x);}void write(char*x){wcs(x);}void write(const char*x){wcs(x);}void write(string&x){ws(x);}
template<typename T,typename...Ts>void write(T&&x,Ts&&...xs){write(x);for(const char*_p=_delimiter;*_p;_putchar(*_p++));write(forward<Ts>(xs)...);}
void writeln(){_putchar('\n');}template<typename...Ts>void writeln(Ts&&...xs){write(forward<Ts>(xs)...);_putchar('\n');}
void flush(){_flush();}class IOManager{public:~IOManager(){flush();}};unique_ptr<IOManager>iomanager;

#define MAXNKQ 300005

struct Store {
    int x, k, yl, yr;
} S[MAXNKQ];

struct Query {
    int x, y, ind;
    
    bool operator < (const Query &q) const {
        return x < q.x;
    }
} QS[MAXNKQ];

struct Interval {
    int xl, xr, y;
    
    bool operator < (const Interval &i) const {
        return xl < i.xl;
    }
};

struct Ray {
    int x, yl, yr, v;
    
    bool operator < (const Ray &r) const {
        return x < r.x;
    }
    
    bool operator > (const Ray &r) const {
        return x > r.x;
    }
};

int N, M, K, Q, temp[MAXNKQ], ans[MAXNKQ], T[MAXNKQ * 2]; 
vector<Store> st[MAXNKQ], en[MAXNKQ];
map<int, int> P[MAXNKQ];
set<Interval> IN[MAXNKQ];
vector<Ray> pos, neg;

void addRay(int k, int xl, int xr, int yl, int yr) {
    if (yl == yr) return;
    yr--;
    if (xl == -1) neg.pb({-1, yl, yr, xr});
    else if (xr == INT_INF) pos.pb({INT_INF, yl, yr, xl});
    else {
        int mx = xl + (xr - xl) / 2;
        pos.pb({mx, yl, yr, xl});
        neg.pb({mx + (xr - xl) % 2, yl, yr, xr});
    }
}

void insertPoint(int k, int x, int y) {
    auto c = prev(IN[k].upper_bound({x, -1, -1}));
    addRay(k, c->xl, c->xr, c->y, y);
    Interval a = {c->xl, x, y}, b = {x, c->xr, y};
    IN[k].erase(c);
    IN[k].insert(a);
    IN[k].insert(b);
}

void erasePoint(int k, int x, int y) {
    auto a = IN[k].lower_bound({x, -1, -1});
    auto b = prev(a);
    addRay(k, b->xl, b->xr, b->y, y);
    addRay(k, a->xl, a->xr, a->y, y);
    Interval c = {b->xl, a->xr, y};
    IN[k].erase(b);
    IN[k].erase(a);
    IN[k].insert(c);
}

void init() {
    FOR(i, 2 * M) T[i] = INT_INF;
}

void update(int l, int r, int v) {
    for (l += M, r += M; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) {
            MIN(T[l], v);
            l++;
        }
        if (!(r & 1)) {
            MIN(T[r], v);
            r--;
        }
    }
}

int query(int i) {
    int q = INT_INF;
    for (i += M; i > 0; i >>= 1) MIN(q, T[i]);
    return q;
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    iomanager.reset(new IOManager());
    read(N, K, Q);
    FOR(i, N) read(S[i].x, S[i].k, S[i].yl, S[i].yr);
    FOR(i, Q) {
        ans[i] = -INT_INF;
        read(QS[i].x, QS[i].y);
        QS[i].ind = i;
        temp[i] = QS[i].y;
    }
    sort(temp, temp + Q);
    M = unique(temp, temp + Q) - temp;
    FOR(i, N) {
        S[i].yl = lower_bound(temp, temp + M, S[i].yl) - temp;
        S[i].yr = upper_bound(temp, temp + M, S[i].yr) - temp;
        st[S[i].yl].pb(S[i]);
        en[S[i].yr].pb(S[i]);
    }
    FOR(i, Q) QS[i].y = lower_bound(temp, temp + M, QS[i].y) - temp;
    For(k, 1, K + 1) {
        IN[k].insert({-1, INT_INF, 0});
        st[0].pb({INT_INF - 1, k, 0, M});
        en[M].pb({INT_INF - 1, k, 0, M});
    }
    M++;
    FOR(y, M) {
        for (Store &s : en[y]) if (--P[s.k][s.x] == 0) erasePoint(s.k, s.x, y);
        for (Store &s : st[y]) if (P[s.k][s.x]++ == 0) insertPoint(s.k, s.x, y);
    }
    sort(all(pos), greater<Ray>());
    sort(all(neg));
    sort(QS, QS + Q);
    init();
    int j = 0;
    FOR(i, Q) {
        while (j < sz(neg) && neg[j].x <= QS[i].x) {
            update(neg[j].yl, neg[j].yr, -neg[j].v);
            j++;
        }
        MAX(ans[QS[i].ind], -query(QS[i].y) - QS[i].x);
    }
    init();
    j = 0;
    REV(i, Q - 1) {
        while (j < sz(pos) && pos[j].x >= QS[i].x) {
            update(pos[j].yl, pos[j].yr, pos[j].v);
            j++;
        }
        MAX(ans[QS[i].ind], QS[i].x - query(QS[i].y));
    }
    FOR(i, Q) writeln(ans[i] >= INT_INF / 2 ? -1 : ans[i]);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20