oj.uz

Submission #388721

# Submission time Handle Problem Language Result Execution time Memory
388721 2021-04-12T16:44:54 Z georgerapeanu Food Court (JOI21_foodcourt) C++11
100 / 100
 881 ms 221028 KB 
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;

class SegmentTree{
    struct node_t{
        long long a,b;///LEAVE a, JOIN b

        node_t operator + (const node_t &other)const{
            node_t ans;
            ans = *this;
            ans.b -= other.a;
            if(ans.b < 0){
                ans.a -= ans.b;
                ans.b = 0;
            }
            ans.b += other.b;
            return ans;
        }

        node_t(){
            a = b = 0;
        }

        node_t(long long a,long long b){
            this->a = a;
            this->b = b;
        }
    };

    int n;
    vector<node_t> aint;

    void propagate(int nod,int st,int dr){
        if(st == dr){
            return ;
        }

        aint[nod * 2] = aint[nod * 2] + aint[nod];
        aint[nod * 2 + 1] = aint[nod * 2 + 1] + aint[nod];
        aint[nod] = node_t();
    }
    
    void update(int nod,int st,int dr,int l,int r,node_t val){
        propagate(nod,st,dr);

        if(dr < l || st > r){
            return ;
        }

        if(l <= st && dr <= r){
            aint[nod] = aint[nod] + val;
            return ;
        }

        int mid = (st + dr) / 2;

        update(nod * 2,st,mid,l,r,val);
        update(nod * 2 + 1,mid + 1,dr,l,r,val);
    }

    node_t access(int nod,int st,int dr,int pos){
        propagate(nod,st,dr);
        if(dr < pos || st > pos){
            return node_t();
        }
        if(st == dr){
            return aint[nod];
        }

        int mid = (st + dr) / 2;

        return access(nod * 2,st,mid,pos) + access(nod * 2 + 1,mid + 1,dr,pos);
    }

public:

    SegmentTree(int n){
        this->n = n;
        this->aint = vector<node_t>(4 * n + 5);
    }

    void add(int l,int r,long long value){
        update(1,1,n,l,r,{0,value});
    }

    void remove(int l,int r,long long value){
        update(1,1,n,l,r,{value,0});
    }

    long long access(int pos){
        return access(1,1,n,pos).b;
    }
};

class FenwickTree{
    int n;
    vector<long long> aib;

    void update(int pos,long long value){
        for(;pos <= n;pos += (-pos) & pos){
            aib[pos] += value;
        }
    }

    long long query(int pos){
        long long ans = 0;

        for(;pos;pos -= (-pos) & pos){
            ans += aib[pos];
        }

        return ans;
    }

public:
 
    FenwickTree(int n){
        this->n = n;
        this->aib = vector<long long>(n + 1);
    }

    void add(int l,int r,long long value){
        update(l,value);
        update(r + 1,-value);
    }

    long long access(int pos){
        return query(pos);
    }
};

class SegmentTree2{///cause why not
    int n;
    vector<pair<long long,int> > aint;
    vector<long long> lazy;

    void propagate(int nod,int st,int dr){
        if(lazy[nod] == 0 || st == dr){
            return ;
        }

        lazy[nod * 2] += lazy[nod];
        lazy[nod * 2 + 1] += lazy[nod];
        aint[nod * 2].first += lazy[nod];
        aint[nod * 2 + 1].first += lazy[nod];
        lazy[nod] = 0;
    }

    void build(int nod,int st,int dr){
        if(st == dr){
            aint[nod] = {0,st};
            return ;
        }

        int mid = (st + dr) / 2;

        build(nod * 2,st,mid);
        build(nod * 2 + 1,mid + 1,dr);

        aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
    }

    void update_range(int nod,int st,int dr,int l,int r,long long value){
        propagate(nod,st,dr);

        if(r < st || l > dr){
            return ;
        }

        if(l <= st && dr <= r){
            aint[nod].first += value;
            lazy[nod] += value;
            return ;
        }

        int mid = (st + dr) / 2;

        update_range(nod * 2,st,mid,l,r,value);
        update_range(nod * 2 + 1,mid + 1,dr,l,r,value);

        aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
    }

    void update_set(int nod,int st,int dr,int pos,long long value){
        propagate(nod,st,dr);

        if(dr < pos || st > pos){
            return ;
        }

        if(st == dr){
            aint[nod].first = value;
            return ;
        }

        int mid = (st + dr) / 2;

        update_set(nod * 2,st,mid,pos,value);
        update_set(nod * 2 + 1,mid + 1,dr,pos,value);

        aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
    }

public:

    SegmentTree2(int n){
        this->n = n;
        aint = vector<pair<long long,int> >(4 * n + 5);
        lazy = vector<long long>(4 * n + 5);
        build(1,1,n);
    }

    void update_range(int l,int r,long long value){
        update_range(1,1,n,l,r,value);
    }

    void update_set(int pos,long long value){
        update_set(1,1,n,pos,value);
    }

    pair<long long,int> query(){
        return aint[1];
    }
};

const int NMAX = 250000;
const int MMAX = 250000;
const int QMAX = 250000;

int n,m,q;

struct query_t{
    int l,r,c;
    long long k;    
};

deque<pair<long long,int> > queries[NMAX + 5];
int answer[QMAX + 5];

const int LEN = 1 << 12;
char buff[LEN];
int ind = LEN - 1;

int i32(){
    int ans = 0;

    while(buff[ind] < '0' || buff[ind] > '9'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    
    while(!(buff[ind] < '0' || buff[ind] > '9')){
        ans = ans * 10 + buff[ind] - '0';
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }

    return ans;
}

long long i64(){
    long long ans = 0;

    while(buff[ind] < '0' || buff[ind] > '9'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    
    while(!(buff[ind] < '0' || buff[ind] > '9')){
        ans = ans * 10 + buff[ind] - '0';
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }

    return ans;
}

int main(){

    n = i32();
    m = i32();
    q = i32();

    vector<query_t> query_list;

    SegmentTree aint(n);
    FenwickTree aib(n);

    for(int i = 1;i <= q;i++){
        int t;
        t = i32();

        if(t == 1){
            int l,r,c;
            long long k;
            l = i32();
            r = i32();
            c = i32();
            k = i64();
            aint.add(l,r,k);
            aib.add(l,r,k);
            query_list.push_back({l,r,c,k});
        }else if(t == 2){
            int l,r;
            long long k;
            l = i32();
            r = i32();
            k = i64();
            aint.remove(l,r,k);
        }else{
            int a;
            long long b;
            a = i32();
            b = i64();
            long long total = aib.access(a);
            long long cnt = aint.access(a);

            if(cnt >= b){
                queries[a].push_back({total - cnt + b,i});
            }else{
                answer[i] = -1;
            }
        }
    }

    SegmentTree2 aint2(n);

    for(int i = 1;i <= n;i++){
        sort(queries[i].begin(),queries[i].end());
        if(queries[i].empty()){
            aint2.update_set(i,1e18);
        }else{
            aint2.update_set(i,queries[i].front().first);
        }
    }
    
    for(auto it:query_list){
        aint2.update_range(it.l,it.r,-it.k);
        while(aint2.query().first <= 0){
            int pos = aint2.query().second;
            answer[queries[pos].front().second] = it.c;
            long long last = queries[pos].front().first;
            queries[pos].pop_front();
            if(queries[pos].empty()){
                aint2.update_set(pos,1e18);
            }else{
                aint2.update_range(pos,pos,queries[pos].front().first - last);
            }
        }
    }

    for(int i = 1;i <= q;i++){
        if(answer[i] != 0){
            printf("%d\n",(answer[i] == -1 ? 0:answer[i]));
        }
    }

    return 0;
}

Compilation message

foodcourt.cpp: In function 'int i32()':
foodcourt.cpp:254:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  254 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
foodcourt.cpp:262:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  262 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'long long int i64()':
foodcourt.cpp:275:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  275 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
foodcourt.cpp:283:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  283 |             fread(buff,1,LEN,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 168792 KB Output is correct
2 Correct 118 ms 168948 KB Output is correct
3 Correct 121 ms 168948 KB Output is correct
4 Correct 117 ms 169012 KB Output is correct
5 Correct 114 ms 168536 KB Output is correct
6 Correct 115 ms 168512 KB Output is correct
7 Correct 119 ms 168952 KB Output is correct
8 Correct 121 ms 168956 KB Output is correct
9 Correct 128 ms 168912 KB Output is correct
10 Correct 117 ms 168900 KB Output is correct
11 Correct 119 ms 169024 KB Output is correct
12 Correct 119 ms 169000 KB Output is correct
13 Correct 119 ms 168900 KB Output is correct
14 Correct 119 ms 168880 KB Output is correct
15 Correct 117 ms 168900 KB Output is correct
16 Correct 120 ms 168900 KB Output is correct
17 Correct 118 ms 168756 KB Output is correct
18 Correct 120 ms 168964 KB Output is correct
19 Correct 112 ms 168900 KB Output is correct
20 Correct 118 ms 169016 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 168792 KB Output is correct
2 Correct 118 ms 168948 KB Output is correct
3 Correct 121 ms 168948 KB Output is correct
4 Correct 117 ms 169012 KB Output is correct
5 Correct 114 ms 168536 KB Output is correct
6 Correct 115 ms 168512 KB Output is correct
7 Correct 119 ms 168952 KB Output is correct
8 Correct 121 ms 168956 KB Output is correct
9 Correct 128 ms 168912 KB Output is correct
10 Correct 117 ms 168900 KB Output is correct
11 Correct 119 ms 169024 KB Output is correct
12 Correct 119 ms 169000 KB Output is correct
13 Correct 119 ms 168900 KB Output is correct
14 Correct 119 ms 168880 KB Output is correct
15 Correct 117 ms 168900 KB Output is correct
16 Correct 120 ms 168900 KB Output is correct
17 Correct 118 ms 168756 KB Output is correct
18 Correct 120 ms 168964 KB Output is correct
19 Correct 112 ms 168900 KB Output is correct
20 Correct 118 ms 169016 KB Output is correct
21 Correct 119 ms 168964 KB Output is correct
22 Correct 119 ms 168972 KB Output is correct
23 Correct 120 ms 168900 KB Output is correct
24 Correct 137 ms 168976 KB Output is correct
25 Correct 119 ms 168644 KB Output is correct
26 Correct 116 ms 168644 KB Output is correct
27 Correct 119 ms 168880 KB Output is correct
28 Correct 119 ms 168900 KB Output is correct
29 Correct 122 ms 168900 KB Output is correct
30 Correct 120 ms 168996 KB Output is correct
31 Correct 119 ms 168968 KB Output is correct
32 Correct 117 ms 168876 KB Output is correct
33 Correct 117 ms 168812 KB Output is correct
34 Correct 121 ms 169000 KB Output is correct
35 Correct 119 ms 168900 KB Output is correct
36 Correct 121 ms 168884 KB Output is correct
37 Correct 117 ms 168900 KB Output is correct
38 Correct 119 ms 169020 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 180696 KB Output is correct
2 Correct 210 ms 180772 KB Output is correct
3 Correct 193 ms 180556 KB Output is correct
4 Correct 212 ms 180804 KB Output is correct
5 Correct 208 ms 180972 KB Output is correct
6 Correct 204 ms 180796 KB Output is correct
7 Correct 144 ms 170136 KB Output is correct
8 Correct 122 ms 170148 KB Output is correct
9 Correct 195 ms 180684 KB Output is correct
10 Correct 195 ms 180672 KB Output is correct
11 Correct 205 ms 180684 KB Output is correct
12 Correct 200 ms 180712 KB Output is correct
13 Correct 187 ms 177404 KB Output is correct
14 Correct 207 ms 180920 KB Output is correct
15 Correct 198 ms 177884 KB Output is correct
16 Correct 212 ms 181384 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 208948 KB Output is correct
2 Correct 623 ms 203172 KB Output is correct
3 Correct 805 ms 213264 KB Output is correct
4 Correct 656 ms 212528 KB Output is correct
5 Correct 617 ms 202632 KB Output is correct
6 Correct 858 ms 214024 KB Output is correct
7 Correct 158 ms 173416 KB Output is correct
8 Correct 164 ms 173372 KB Output is correct
9 Correct 867 ms 214060 KB Output is correct
10 Correct 879 ms 219896 KB Output is correct
11 Correct 760 ms 219136 KB Output is correct
12 Correct 780 ms 219112 KB Output is correct
13 Correct 771 ms 219188 KB Output is correct
14 Correct 772 ms 219188 KB Output is correct
15 Correct 780 ms 219004 KB Output is correct
16 Correct 816 ms 219108 KB Output is correct
17 Correct 802 ms 219004 KB Output is correct
18 Correct 800 ms 219208 KB Output is correct
19 Correct 807 ms 219176 KB Output is correct
20 Correct 766 ms 219060 KB Output is correct
21 Correct 804 ms 219148 KB Output is correct
22 Correct 804 ms 219120 KB Output is correct
23 Correct 816 ms 219028 KB Output is correct
24 Correct 801 ms 219100 KB Output is correct
25 Correct 643 ms 209124 KB Output is correct
26 Correct 675 ms 218564 KB Output is correct
27 Correct 603 ms 220028 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 168792 KB Output is correct
2 Correct 118 ms 168948 KB Output is correct
3 Correct 121 ms 168948 KB Output is correct
4 Correct 117 ms 169012 KB Output is correct
5 Correct 114 ms 168536 KB Output is correct
6 Correct 115 ms 168512 KB Output is correct
7 Correct 119 ms 168952 KB Output is correct
8 Correct 121 ms 168956 KB Output is correct
9 Correct 128 ms 168912 KB Output is correct
10 Correct 117 ms 168900 KB Output is correct
11 Correct 119 ms 169024 KB Output is correct
12 Correct 119 ms 169000 KB Output is correct
13 Correct 119 ms 168900 KB Output is correct
14 Correct 119 ms 168880 KB Output is correct
15 Correct 117 ms 168900 KB Output is correct
16 Correct 120 ms 168900 KB Output is correct
17 Correct 118 ms 168756 KB Output is correct
18 Correct 120 ms 168964 KB Output is correct
19 Correct 112 ms 168900 KB Output is correct
20 Correct 118 ms 169016 KB Output is correct
21 Correct 207 ms 180696 KB Output is correct
22 Correct 210 ms 180772 KB Output is correct
23 Correct 193 ms 180556 KB Output is correct
24 Correct 212 ms 180804 KB Output is correct
25 Correct 208 ms 180972 KB Output is correct
26 Correct 204 ms 180796 KB Output is correct
27 Correct 144 ms 170136 KB Output is correct
28 Correct 122 ms 170148 KB Output is correct
29 Correct 195 ms 180684 KB Output is correct
30 Correct 195 ms 180672 KB Output is correct
31 Correct 205 ms 180684 KB Output is correct
32 Correct 200 ms 180712 KB Output is correct
33 Correct 187 ms 177404 KB Output is correct
34 Correct 207 ms 180920 KB Output is correct
35 Correct 198 ms 177884 KB Output is correct
36 Correct 212 ms 181384 KB Output is correct
37 Correct 231 ms 179280 KB Output is correct
38 Correct 226 ms 179408 KB Output is correct
39 Correct 133 ms 169816 KB Output is correct
40 Correct 140 ms 169808 KB Output is correct
41 Correct 236 ms 180412 KB Output is correct
42 Correct 235 ms 180480 KB Output is correct
43 Correct 243 ms 180476 KB Output is correct
44 Correct 239 ms 180464 KB Output is correct
45 Correct 240 ms 180412 KB Output is correct
46 Correct 242 ms 180424 KB Output is correct
47 Correct 180 ms 180412 KB Output is correct
48 Correct 234 ms 180440 KB Output is correct
49 Correct 203 ms 177000 KB Output is correct
50 Correct 225 ms 180160 KB Output is correct
51 Correct 242 ms 180540 KB Output is correct
52 Correct 240 ms 180528 KB Output is correct
53 Correct 192 ms 179424 KB Output is correct
54 Correct 215 ms 181356 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 180284 KB Output is correct
2 Correct 250 ms 178920 KB Output is correct
3 Correct 260 ms 180756 KB Output is correct
4 Correct 218 ms 179744 KB Output is correct
5 Correct 234 ms 180188 KB Output is correct
6 Correct 259 ms 180608 KB Output is correct
7 Correct 138 ms 170092 KB Output is correct
8 Correct 138 ms 169980 KB Output is correct
9 Correct 200 ms 180868 KB Output is correct
10 Correct 211 ms 179032 KB Output is correct
11 Correct 243 ms 180668 KB Output is correct
12 Correct 247 ms 180668 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 168792 KB Output is correct
2 Correct 118 ms 168948 KB Output is correct
3 Correct 121 ms 168948 KB Output is correct
4 Correct 117 ms 169012 KB Output is correct
5 Correct 114 ms 168536 KB Output is correct
6 Correct 115 ms 168512 KB Output is correct
7 Correct 119 ms 168952 KB Output is correct
8 Correct 121 ms 168956 KB Output is correct
9 Correct 128 ms 168912 KB Output is correct
10 Correct 117 ms 168900 KB Output is correct
11 Correct 119 ms 169024 KB Output is correct
12 Correct 119 ms 169000 KB Output is correct
13 Correct 119 ms 168900 KB Output is correct
14 Correct 119 ms 168880 KB Output is correct
15 Correct 117 ms 168900 KB Output is correct
16 Correct 120 ms 168900 KB Output is correct
17 Correct 118 ms 168756 KB Output is correct
18 Correct 120 ms 168964 KB Output is correct
19 Correct 112 ms 168900 KB Output is correct
20 Correct 118 ms 169016 KB Output is correct
21 Correct 119 ms 168964 KB Output is correct
22 Correct 119 ms 168972 KB Output is correct
23 Correct 120 ms 168900 KB Output is correct
24 Correct 137 ms 168976 KB Output is correct
25 Correct 119 ms 168644 KB Output is correct
26 Correct 116 ms 168644 KB Output is correct
27 Correct 119 ms 168880 KB Output is correct
28 Correct 119 ms 168900 KB Output is correct
29 Correct 122 ms 168900 KB Output is correct
30 Correct 120 ms 168996 KB Output is correct
31 Correct 119 ms 168968 KB Output is correct
32 Correct 117 ms 168876 KB Output is correct
33 Correct 117 ms 168812 KB Output is correct
34 Correct 121 ms 169000 KB Output is correct
35 Correct 119 ms 168900 KB Output is correct
36 Correct 121 ms 168884 KB Output is correct
37 Correct 117 ms 168900 KB Output is correct
38 Correct 119 ms 169020 KB Output is correct
39 Correct 207 ms 180696 KB Output is correct
40 Correct 210 ms 180772 KB Output is correct
41 Correct 193 ms 180556 KB Output is correct
42 Correct 212 ms 180804 KB Output is correct
43 Correct 208 ms 180972 KB Output is correct
44 Correct 204 ms 180796 KB Output is correct
45 Correct 144 ms 170136 KB Output is correct
46 Correct 122 ms 170148 KB Output is correct
47 Correct 195 ms 180684 KB Output is correct
48 Correct 195 ms 180672 KB Output is correct
49 Correct 205 ms 180684 KB Output is correct
50 Correct 200 ms 180712 KB Output is correct
51 Correct 187 ms 177404 KB Output is correct
52 Correct 207 ms 180920 KB Output is correct
53 Correct 198 ms 177884 KB Output is correct
54 Correct 212 ms 181384 KB Output is correct
55 Correct 231 ms 179280 KB Output is correct
56 Correct 226 ms 179408 KB Output is correct
57 Correct 133 ms 169816 KB Output is correct
58 Correct 140 ms 169808 KB Output is correct
59 Correct 236 ms 180412 KB Output is correct
60 Correct 235 ms 180480 KB Output is correct
61 Correct 243 ms 180476 KB Output is correct
62 Correct 239 ms 180464 KB Output is correct
63 Correct 240 ms 180412 KB Output is correct
64 Correct 242 ms 180424 KB Output is correct
65 Correct 180 ms 180412 KB Output is correct
66 Correct 234 ms 180440 KB Output is correct
67 Correct 203 ms 177000 KB Output is correct
68 Correct 225 ms 180160 KB Output is correct
69 Correct 242 ms 180540 KB Output is correct
70 Correct 240 ms 180528 KB Output is correct
71 Correct 192 ms 179424 KB Output is correct
72 Correct 215 ms 181356 KB Output is correct
73 Correct 244 ms 180284 KB Output is correct
74 Correct 250 ms 178920 KB Output is correct
75 Correct 260 ms 180756 KB Output is correct
76 Correct 218 ms 179744 KB Output is correct
77 Correct 234 ms 180188 KB Output is correct
78 Correct 259 ms 180608 KB Output is correct
79 Correct 138 ms 170092 KB Output is correct
80 Correct 138 ms 169980 KB Output is correct
81 Correct 200 ms 180868 KB Output is correct
82 Correct 211 ms 179032 KB Output is correct
83 Correct 243 ms 180668 KB Output is correct
84 Correct 247 ms 180668 KB Output is correct
85 Correct 229 ms 177980 KB Output is correct
86 Correct 248 ms 180276 KB Output is correct
87 Correct 240 ms 179764 KB Output is correct
88 Correct 260 ms 180524 KB Output is correct
89 Correct 204 ms 177772 KB Output is correct
90 Correct 242 ms 180224 KB Output is correct
91 Correct 211 ms 176528 KB Output is correct
92 Correct 220 ms 176568 KB Output is correct
93 Correct 244 ms 180380 KB Output is correct
94 Correct 240 ms 180252 KB Output is correct
95 Correct 239 ms 179336 KB Output is correct
96 Correct 249 ms 180228 KB Output is correct
97 Correct 242 ms 180244 KB Output is correct
98 Correct 224 ms 177036 KB Output is correct
99 Correct 182 ms 180156 KB Output is correct
100 Correct 215 ms 178492 KB Output is correct
101 Correct 235 ms 180296 KB Output is correct
102 Correct 216 ms 180536 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 168792 KB Output is correct
2 Correct 118 ms 168948 KB Output is correct
3 Correct 121 ms 168948 KB Output is correct
4 Correct 117 ms 169012 KB Output is correct
5 Correct 114 ms 168536 KB Output is correct
6 Correct 115 ms 168512 KB Output is correct
7 Correct 119 ms 168952 KB Output is correct
8 Correct 121 ms 168956 KB Output is correct
9 Correct 128 ms 168912 KB Output is correct
10 Correct 117 ms 168900 KB Output is correct
11 Correct 119 ms 169024 KB Output is correct
12 Correct 119 ms 169000 KB Output is correct
13 Correct 119 ms 168900 KB Output is correct
14 Correct 119 ms 168880 KB Output is correct
15 Correct 117 ms 168900 KB Output is correct
16 Correct 120 ms 168900 KB Output is correct
17 Correct 118 ms 168756 KB Output is correct
18 Correct 120 ms 168964 KB Output is correct
19 Correct 112 ms 168900 KB Output is correct
20 Correct 118 ms 169016 KB Output is correct
21 Correct 119 ms 168964 KB Output is correct
22 Correct 119 ms 168972 KB Output is correct
23 Correct 120 ms 168900 KB Output is correct
24 Correct 137 ms 168976 KB Output is correct
25 Correct 119 ms 168644 KB Output is correct
26 Correct 116 ms 168644 KB Output is correct
27 Correct 119 ms 168880 KB Output is correct
28 Correct 119 ms 168900 KB Output is correct
29 Correct 122 ms 168900 KB Output is correct
30 Correct 120 ms 168996 KB Output is correct
31 Correct 119 ms 168968 KB Output is correct
32 Correct 117 ms 168876 KB Output is correct
33 Correct 117 ms 168812 KB Output is correct
34 Correct 121 ms 169000 KB Output is correct
35 Correct 119 ms 168900 KB Output is correct
36 Correct 121 ms 168884 KB Output is correct
37 Correct 117 ms 168900 KB Output is correct
38 Correct 119 ms 169020 KB Output is correct
39 Correct 207 ms 180696 KB Output is correct
40 Correct 210 ms 180772 KB Output is correct
41 Correct 193 ms 180556 KB Output is correct
42 Correct 212 ms 180804 KB Output is correct
43 Correct 208 ms 180972 KB Output is correct
44 Correct 204 ms 180796 KB Output is correct
45 Correct 144 ms 170136 KB Output is correct
46 Correct 122 ms 170148 KB Output is correct
47 Correct 195 ms 180684 KB Output is correct
48 Correct 195 ms 180672 KB Output is correct
49 Correct 205 ms 180684 KB Output is correct
50 Correct 200 ms 180712 KB Output is correct
51 Correct 187 ms 177404 KB Output is correct
52 Correct 207 ms 180920 KB Output is correct
53 Correct 198 ms 177884 KB Output is correct
54 Correct 212 ms 181384 KB Output is correct
55 Correct 757 ms 208948 KB Output is correct
56 Correct 623 ms 203172 KB Output is correct
57 Correct 805 ms 213264 KB Output is correct
58 Correct 656 ms 212528 KB Output is correct
59 Correct 617 ms 202632 KB Output is correct
60 Correct 858 ms 214024 KB Output is correct
61 Correct 158 ms 173416 KB Output is correct
62 Correct 164 ms 173372 KB Output is correct
63 Correct 867 ms 214060 KB Output is correct
64 Correct 879 ms 219896 KB Output is correct
65 Correct 760 ms 219136 KB Output is correct
66 Correct 780 ms 219112 KB Output is correct
67 Correct 771 ms 219188 KB Output is correct
68 Correct 772 ms 219188 KB Output is correct
69 Correct 780 ms 219004 KB Output is correct
70 Correct 816 ms 219108 KB Output is correct
71 Correct 802 ms 219004 KB Output is correct
72 Correct 800 ms 219208 KB Output is correct
73 Correct 807 ms 219176 KB Output is correct
74 Correct 766 ms 219060 KB Output is correct
75 Correct 804 ms 219148 KB Output is correct
76 Correct 804 ms 219120 KB Output is correct
77 Correct 816 ms 219028 KB Output is correct
78 Correct 801 ms 219100 KB Output is correct
79 Correct 643 ms 209124 KB Output is correct
80 Correct 675 ms 218564 KB Output is correct
81 Correct 603 ms 220028 KB Output is correct
82 Correct 231 ms 179280 KB Output is correct
83 Correct 226 ms 179408 KB Output is correct
84 Correct 133 ms 169816 KB Output is correct
85 Correct 140 ms 169808 KB Output is correct
86 Correct 236 ms 180412 KB Output is correct
87 Correct 235 ms 180480 KB Output is correct
88 Correct 243 ms 180476 KB Output is correct
89 Correct 239 ms 180464 KB Output is correct
90 Correct 240 ms 180412 KB Output is correct
91 Correct 242 ms 180424 KB Output is correct
92 Correct 180 ms 180412 KB Output is correct
93 Correct 234 ms 180440 KB Output is correct
94 Correct 203 ms 177000 KB Output is correct
95 Correct 225 ms 180160 KB Output is correct
96 Correct 242 ms 180540 KB Output is correct
97 Correct 240 ms 180528 KB Output is correct
98 Correct 192 ms 179424 KB Output is correct
99 Correct 215 ms 181356 KB Output is correct
100 Correct 244 ms 180284 KB Output is correct
101 Correct 250 ms 178920 KB Output is correct
102 Correct 260 ms 180756 KB Output is correct
103 Correct 218 ms 179744 KB Output is correct
104 Correct 234 ms 180188 KB Output is correct
105 Correct 259 ms 180608 KB Output is correct
106 Correct 138 ms 170092 KB Output is correct
107 Correct 138 ms 169980 KB Output is correct
108 Correct 200 ms 180868 KB Output is correct
109 Correct 211 ms 179032 KB Output is correct
110 Correct 243 ms 180668 KB Output is correct
111 Correct 247 ms 180668 KB Output is correct
112 Correct 229 ms 177980 KB Output is correct
113 Correct 248 ms 180276 KB Output is correct
114 Correct 240 ms 179764 KB Output is correct
115 Correct 260 ms 180524 KB Output is correct
116 Correct 204 ms 177772 KB Output is correct
117 Correct 242 ms 180224 KB Output is correct
118 Correct 211 ms 176528 KB Output is correct
119 Correct 220 ms 176568 KB Output is correct
120 Correct 244 ms 180380 KB Output is correct
121 Correct 240 ms 180252 KB Output is correct
122 Correct 239 ms 179336 KB Output is correct
123 Correct 249 ms 180228 KB Output is correct
124 Correct 242 ms 180244 KB Output is correct
125 Correct 224 ms 177036 KB Output is correct
126 Correct 182 ms 180156 KB Output is correct
127 Correct 215 ms 178492 KB Output is correct
128 Correct 235 ms 180296 KB Output is correct
129 Correct 216 ms 180536 KB Output is correct
130 Correct 817 ms 218372 KB Output is correct
131 Correct 605 ms 206240 KB Output is correct
132 Correct 789 ms 219616 KB Output is correct
133 Correct 814 ms 218656 KB Output is correct
134 Correct 744 ms 217584 KB Output is correct
135 Correct 841 ms 220748 KB Output is correct
136 Correct 881 ms 220828 KB Output is correct
137 Correct 869 ms 220840 KB Output is correct
138 Correct 754 ms 219820 KB Output is correct
139 Correct 779 ms 219796 KB Output is correct
140 Correct 786 ms 219796 KB Output is correct
141 Correct 794 ms 219732 KB Output is correct
142 Correct 826 ms 219708 KB Output is correct
143 Correct 806 ms 219672 KB Output is correct
144 Correct 803 ms 219760 KB Output is correct
145 Correct 793 ms 219776 KB Output is correct
146 Correct 821 ms 219756 KB Output is correct
147 Correct 785 ms 219720 KB Output is correct
148 Correct 781 ms 219700 KB Output is correct
149 Correct 810 ms 219728 KB Output is correct
150 Correct 439 ms 218756 KB Output is correct
151 Correct 685 ms 219144 KB Output is correct
152 Correct 675 ms 219188 KB Output is correct
153 Correct 602 ms 221028 KB Output is correct