oj.uz

Submission #65165

# Submission time Handle Problem Language Result Execution time Memory
65165 2018-08-06T22:50:08 Z wleung_bvg New Home (APIO18_new_home) C++14
100 / 100
 2962 ms 973848 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42616 KB Output is correct
2 Correct 43 ms 42804 KB Output is correct
3 Correct 48 ms 42804 KB Output is correct
4 Correct 46 ms 42804 KB Output is correct
5 Correct 45 ms 42952 KB Output is correct
6 Correct 46 ms 43124 KB Output is correct
7 Correct 46 ms 43228 KB Output is correct
8 Correct 43 ms 43228 KB Output is correct
9 Correct 46 ms 43288 KB Output is correct
10 Correct 42 ms 43296 KB Output is correct
11 Correct 45 ms 43296 KB Output is correct
12 Correct 45 ms 43296 KB Output is correct
13 Correct 44 ms 43296 KB Output is correct
14 Correct 43 ms 43336 KB Output is correct
15 Correct 84 ms 43364 KB Output is correct
16 Correct 42 ms 43504 KB Output is correct
17 Correct 41 ms 43504 KB Output is correct
18 Correct 43 ms 43504 KB Output is correct
19 Correct 42 ms 43560 KB Output is correct
20 Correct 41 ms 43560 KB Output is correct
21 Correct 43 ms 43600 KB Output is correct
22 Correct 43 ms 43616 KB Output is correct
23 Correct 44 ms 43616 KB Output is correct
24 Correct 44 ms 43656 KB Output is correct
25 Correct 46 ms 43656 KB Output is correct
26 Correct 43 ms 43696 KB Output is correct
27 Correct 43 ms 43696 KB Output is correct
28 Correct 41 ms 43696 KB Output is correct
29 Correct 41 ms 43696 KB Output is correct
30 Correct 48 ms 43696 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42616 KB Output is correct
2 Correct 43 ms 42804 KB Output is correct
3 Correct 48 ms 42804 KB Output is correct
4 Correct 46 ms 42804 KB Output is correct
5 Correct 45 ms 42952 KB Output is correct
6 Correct 46 ms 43124 KB Output is correct
7 Correct 46 ms 43228 KB Output is correct
8 Correct 43 ms 43228 KB Output is correct
9 Correct 46 ms 43288 KB Output is correct
10 Correct 42 ms 43296 KB Output is correct
11 Correct 45 ms 43296 KB Output is correct
12 Correct 45 ms 43296 KB Output is correct
13 Correct 44 ms 43296 KB Output is correct
14 Correct 43 ms 43336 KB Output is correct
15 Correct 84 ms 43364 KB Output is correct
16 Correct 42 ms 43504 KB Output is correct
17 Correct 41 ms 43504 KB Output is correct
18 Correct 43 ms 43504 KB Output is correct
19 Correct 42 ms 43560 KB Output is correct
20 Correct 41 ms 43560 KB Output is correct
21 Correct 43 ms 43600 KB Output is correct
22 Correct 43 ms 43616 KB Output is correct
23 Correct 44 ms 43616 KB Output is correct
24 Correct 44 ms 43656 KB Output is correct
25 Correct 46 ms 43656 KB Output is correct
26 Correct 43 ms 43696 KB Output is correct
27 Correct 43 ms 43696 KB Output is correct
28 Correct 41 ms 43696 KB Output is correct
29 Correct 41 ms 43696 KB Output is correct
30 Correct 48 ms 43696 KB Output is correct
31 Correct 407 ms 64772 KB Output is correct
32 Correct 76 ms 64772 KB Output is correct
33 Correct 469 ms 65584 KB Output is correct
34 Correct 379 ms 68736 KB Output is correct
35 Correct 515 ms 74528 KB Output is correct
36 Correct 490 ms 77240 KB Output is correct
37 Correct 297 ms 77240 KB Output is correct
38 Correct 312 ms 79648 KB Output is correct
39 Correct 240 ms 82092 KB Output is correct
40 Correct 255 ms 84956 KB Output is correct
41 Correct 280 ms 87328 KB Output is correct
42 Correct 286 ms 90352 KB Output is correct
43 Correct 62 ms 90352 KB Output is correct
44 Correct 283 ms 95572 KB Output is correct
45 Correct 280 ms 98580 KB Output is correct
46 Correct 259 ms 101220 KB Output is correct
47 Correct 189 ms 102832 KB Output is correct
48 Correct 198 ms 105684 KB Output is correct
49 Correct 196 ms 108952 KB Output is correct
50 Correct 255 ms 112196 KB Output is correct
51 Correct 190 ms 114532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1496 ms 202872 KB Output is correct
2 Correct 2417 ms 204156 KB Output is correct
3 Correct 1561 ms 300632 KB Output is correct
4 Correct 1484 ms 300632 KB Output is correct
5 Correct 2453 ms 300632 KB Output is correct
6 Correct 2535 ms 300632 KB Output is correct
7 Correct 895 ms 332712 KB Output is correct
8 Correct 829 ms 332712 KB Output is correct
9 Correct 750 ms 332712 KB Output is correct
10 Correct 906 ms 332712 KB Output is correct
11 Correct 847 ms 332712 KB Output is correct
12 Correct 718 ms 335628 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2262 ms 354952 KB Output is correct
2 Correct 161 ms 354952 KB Output is correct
3 Correct 2766 ms 370032 KB Output is correct
4 Correct 2106 ms 468080 KB Output is correct
5 Correct 1969 ms 468080 KB Output is correct
6 Correct 1978 ms 468080 KB Output is correct
7 Correct 2962 ms 468080 KB Output is correct
8 Correct 2862 ms 468080 KB Output is correct
9 Correct 1464 ms 533552 KB Output is correct
10 Correct 1687 ms 533552 KB Output is correct
11 Correct 1805 ms 533552 KB Output is correct
12 Correct 2147 ms 533552 KB Output is correct
13 Correct 947 ms 533552 KB Output is correct
14 Correct 970 ms 533552 KB Output is correct
15 Correct 1112 ms 533552 KB Output is correct
16 Correct 1226 ms 535964 KB Output is correct
17 Correct 1196 ms 546744 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42616 KB Output is correct
2 Correct 43 ms 42804 KB Output is correct
3 Correct 48 ms 42804 KB Output is correct
4 Correct 46 ms 42804 KB Output is correct
5 Correct 45 ms 42952 KB Output is correct
6 Correct 46 ms 43124 KB Output is correct
7 Correct 46 ms 43228 KB Output is correct
8 Correct 43 ms 43228 KB Output is correct
9 Correct 46 ms 43288 KB Output is correct
10 Correct 42 ms 43296 KB Output is correct
11 Correct 45 ms 43296 KB Output is correct
12 Correct 45 ms 43296 KB Output is correct
13 Correct 44 ms 43296 KB Output is correct
14 Correct 43 ms 43336 KB Output is correct
15 Correct 84 ms 43364 KB Output is correct
16 Correct 42 ms 43504 KB Output is correct
17 Correct 41 ms 43504 KB Output is correct
18 Correct 43 ms 43504 KB Output is correct
19 Correct 42 ms 43560 KB Output is correct
20 Correct 41 ms 43560 KB Output is correct
21 Correct 43 ms 43600 KB Output is correct
22 Correct 43 ms 43616 KB Output is correct
23 Correct 44 ms 43616 KB Output is correct
24 Correct 44 ms 43656 KB Output is correct
25 Correct 46 ms 43656 KB Output is correct
26 Correct 43 ms 43696 KB Output is correct
27 Correct 43 ms 43696 KB Output is correct
28 Correct 41 ms 43696 KB Output is correct
29 Correct 41 ms 43696 KB Output is correct
30 Correct 48 ms 43696 KB Output is correct
31 Correct 407 ms 64772 KB Output is correct
32 Correct 76 ms 64772 KB Output is correct
33 Correct 469 ms 65584 KB Output is correct
34 Correct 379 ms 68736 KB Output is correct
35 Correct 515 ms 74528 KB Output is correct
36 Correct 490 ms 77240 KB Output is correct
37 Correct 297 ms 77240 KB Output is correct
38 Correct 312 ms 79648 KB Output is correct
39 Correct 240 ms 82092 KB Output is correct
40 Correct 255 ms 84956 KB Output is correct
41 Correct 280 ms 87328 KB Output is correct
42 Correct 286 ms 90352 KB Output is correct
43 Correct 62 ms 90352 KB Output is correct
44 Correct 283 ms 95572 KB Output is correct
45 Correct 280 ms 98580 KB Output is correct
46 Correct 259 ms 101220 KB Output is correct
47 Correct 189 ms 102832 KB Output is correct
48 Correct 198 ms 105684 KB Output is correct
49 Correct 196 ms 108952 KB Output is correct
50 Correct 255 ms 112196 KB Output is correct
51 Correct 190 ms 114532 KB Output is correct
52 Correct 402 ms 546744 KB Output is correct
53 Correct 374 ms 546744 KB Output is correct
54 Correct 334 ms 546744 KB Output is correct
55 Correct 287 ms 546744 KB Output is correct
56 Correct 274 ms 546744 KB Output is correct
57 Correct 277 ms 546744 KB Output is correct
58 Correct 282 ms 546744 KB Output is correct
59 Correct 322 ms 546744 KB Output is correct
60 Correct 275 ms 546744 KB Output is correct
61 Correct 127 ms 546744 KB Output is correct
62 Correct 379 ms 546744 KB Output is correct
63 Correct 353 ms 546744 KB Output is correct
64 Correct 319 ms 546744 KB Output is correct
65 Correct 317 ms 546744 KB Output is correct
66 Correct 257 ms 546744 KB Output is correct
67 Correct 203 ms 546744 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42616 KB Output is correct
2 Correct 43 ms 42804 KB Output is correct
3 Correct 48 ms 42804 KB Output is correct
4 Correct 46 ms 42804 KB Output is correct
5 Correct 45 ms 42952 KB Output is correct
6 Correct 46 ms 43124 KB Output is correct
7 Correct 46 ms 43228 KB Output is correct
8 Correct 43 ms 43228 KB Output is correct
9 Correct 46 ms 43288 KB Output is correct
10 Correct 42 ms 43296 KB Output is correct
11 Correct 45 ms 43296 KB Output is correct
12 Correct 45 ms 43296 KB Output is correct
13 Correct 44 ms 43296 KB Output is correct
14 Correct 43 ms 43336 KB Output is correct
15 Correct 84 ms 43364 KB Output is correct
16 Correct 42 ms 43504 KB Output is correct
17 Correct 41 ms 43504 KB Output is correct
18 Correct 43 ms 43504 KB Output is correct
19 Correct 42 ms 43560 KB Output is correct
20 Correct 41 ms 43560 KB Output is correct
21 Correct 43 ms 43600 KB Output is correct
22 Correct 43 ms 43616 KB Output is correct
23 Correct 44 ms 43616 KB Output is correct
24 Correct 44 ms 43656 KB Output is correct
25 Correct 46 ms 43656 KB Output is correct
26 Correct 43 ms 43696 KB Output is correct
27 Correct 43 ms 43696 KB Output is correct
28 Correct 41 ms 43696 KB Output is correct
29 Correct 41 ms 43696 KB Output is correct
30 Correct 48 ms 43696 KB Output is correct
31 Correct 407 ms 64772 KB Output is correct
32 Correct 76 ms 64772 KB Output is correct
33 Correct 469 ms 65584 KB Output is correct
34 Correct 379 ms 68736 KB Output is correct
35 Correct 515 ms 74528 KB Output is correct
36 Correct 490 ms 77240 KB Output is correct
37 Correct 297 ms 77240 KB Output is correct
38 Correct 312 ms 79648 KB Output is correct
39 Correct 240 ms 82092 KB Output is correct
40 Correct 255 ms 84956 KB Output is correct
41 Correct 280 ms 87328 KB Output is correct
42 Correct 286 ms 90352 KB Output is correct
43 Correct 62 ms 90352 KB Output is correct
44 Correct 283 ms 95572 KB Output is correct
45 Correct 280 ms 98580 KB Output is correct
46 Correct 259 ms 101220 KB Output is correct
47 Correct 189 ms 102832 KB Output is correct
48 Correct 198 ms 105684 KB Output is correct
49 Correct 196 ms 108952 KB Output is correct
50 Correct 255 ms 112196 KB Output is correct
51 Correct 190 ms 114532 KB Output is correct
52 Correct 1496 ms 202872 KB Output is correct
53 Correct 2417 ms 204156 KB Output is correct
54 Correct 1561 ms 300632 KB Output is correct
55 Correct 1484 ms 300632 KB Output is correct
56 Correct 2453 ms 300632 KB Output is correct
57 Correct 2535 ms 300632 KB Output is correct
58 Correct 895 ms 332712 KB Output is correct
59 Correct 829 ms 332712 KB Output is correct
60 Correct 750 ms 332712 KB Output is correct
61 Correct 906 ms 332712 KB Output is correct
62 Correct 847 ms 332712 KB Output is correct
63 Correct 718 ms 335628 KB Output is correct
64 Correct 2262 ms 354952 KB Output is correct
65 Correct 161 ms 354952 KB Output is correct
66 Correct 2766 ms 370032 KB Output is correct
67 Correct 2106 ms 468080 KB Output is correct
68 Correct 1969 ms 468080 KB Output is correct
69 Correct 1978 ms 468080 KB Output is correct
70 Correct 2962 ms 468080 KB Output is correct
71 Correct 2862 ms 468080 KB Output is correct
72 Correct 1464 ms 533552 KB Output is correct
73 Correct 1687 ms 533552 KB Output is correct
74 Correct 1805 ms 533552 KB Output is correct
75 Correct 2147 ms 533552 KB Output is correct
76 Correct 947 ms 533552 KB Output is correct
77 Correct 970 ms 533552 KB Output is correct
78 Correct 1112 ms 533552 KB Output is correct
79 Correct 1226 ms 535964 KB Output is correct
80 Correct 1196 ms 546744 KB Output is correct
81 Correct 402 ms 546744 KB Output is correct
82 Correct 374 ms 546744 KB Output is correct
83 Correct 334 ms 546744 KB Output is correct
84 Correct 287 ms 546744 KB Output is correct
85 Correct 274 ms 546744 KB Output is correct
86 Correct 277 ms 546744 KB Output is correct
87 Correct 282 ms 546744 KB Output is correct
88 Correct 322 ms 546744 KB Output is correct
89 Correct 275 ms 546744 KB Output is correct
90 Correct 127 ms 546744 KB Output is correct
91 Correct 379 ms 546744 KB Output is correct
92 Correct 353 ms 546744 KB Output is correct
93 Correct 319 ms 546744 KB Output is correct
94 Correct 317 ms 546744 KB Output is correct
95 Correct 257 ms 546744 KB Output is correct
96 Correct 203 ms 546744 KB Output is correct
97 Correct 2284 ms 696428 KB Output is correct
98 Correct 224 ms 696428 KB Output is correct
99 Correct 2803 ms 696428 KB Output is correct
100 Correct 2072 ms 714264 KB Output is correct
101 Correct 1927 ms 714264 KB Output is correct
102 Correct 2809 ms 714264 KB Output is correct
103 Correct 1875 ms 714264 KB Output is correct
104 Correct 1949 ms 714264 KB Output is correct
105 Correct 1404 ms 714264 KB Output is correct
106 Correct 1442 ms 723440 KB Output is correct
107 Correct 1570 ms 763200 KB Output is correct
108 Correct 1575 ms 805732 KB Output is correct
109 Correct 1530 ms 805732 KB Output is correct
110 Correct 1690 ms 809620 KB Output is correct
111 Correct 1962 ms 852976 KB Output is correct
112 Correct 1895 ms 852976 KB Output is correct
113 Correct 582 ms 893144 KB Output is correct
114 Correct 2376 ms 933932 KB Output is correct
115 Correct 2151 ms 933932 KB Output is correct
116 Correct 2129 ms 933932 KB Output is correct
117 Correct 2104 ms 933932 KB Output is correct
118 Correct 1882 ms 933932 KB Output is correct
119 Correct 1215 ms 933932 KB Output is correct
120 Correct 739 ms 933932 KB Output is correct
121 Correct 927 ms 933932 KB Output is correct
122 Correct 785 ms 938412 KB Output is correct
123 Correct 933 ms 949580 KB Output is correct
124 Correct 1107 ms 958752 KB Output is correct
125 Correct 908 ms 965460 KB Output is correct
126 Correct 1182 ms 973848 KB Output is correct