oj.uz

Submission #1031071

# Submission time Handle Problem Language Result Execution time Memory
1031071 2024-07-22T14:22:20 Z Antekb JOI tour (JOI24_joitour) C++17
100 / 100
 2270 ms 522528 KB 
#include "bits/stdc++.h"	/** keep-include */
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

#include "joitour.h"

const int N=2e5+5;

ll result;
int typ[N];


struct drzewo{
    vi real_name;
    vi siz, par, pre, post, subtree, order;
    vector<vi> E;
    int root=-1, real_root;
    int n;
    vi ile[2];
    vector<ll> sum[2];
    ll iles[2]={}, sums[2]={};
    ll zle=0;
    ll res=0;
    int new_name(int v){
        return lower_bound(all(real_name), v)-real_name.begin();
    }
    void dfs_cent(int v){
        siz[v]=1;
        bool ok=1;
        for(int u:E[v]){
            if(u!=par[v]){
                par[u]=v;
                dfs_cent(u);
                siz[v]+=siz[u];
                if(siz[u]*2>n)ok=0;
            }
        }
        if(ok && 2*(n-siz[v])<=n){
            root=v;
        }
    }
    void dfs_init(int v, int sub=-1){
        deb(v, sub, order, root, E[v]);
        pre[v]=order.size();
        order.pb(v);
        int cnt=0;
        if(v!=root){
            subtree[v]=sub;
            for(int &u:E[v])if(u==par[v])swap(u, E[v].back());
            E[v].pop_back();
        }
        for(int u:E[v]){
            par[u]=v;
            if(v==root)dfs_init(u, cnt);
            else dfs_init(u, sub);
            cnt++;
        }
        post[v]=order.size();
    }
    pair<int, ll> licz(int v, int lbl, int num){//num - liczba 1
        pair<int, ll> a;
        for(int u:E[v]){
            auto b=licz(u, lbl, num+(typ[real_name[v]]==1));
            a.st+=b.st;
            a.nd+=b.nd;
        }
        if(typ[real_name[v]]==lbl*2){
            a.st++;
            a.nd+=num;
        }
        return a;
    }
    void calc(){
        result-=res;
        res=0;
        iles[0]=0;
        iles[1]=0;
        sums[0]=0;
        sums[1]=0;
        zle=0;
        for(int i=0; i<E[root].size(); i++){
            auto a=licz(E[root][i], 0, 0);
            auto b=licz(E[root][i], 1, 0);
            ile[0][i]={a.st};
            ile[1][i]={b.st};
            sum[0][i]={a.nd};
            sum[1][i]={b.nd};
            iles[0]+=a.st;
            iles[1]+=b.st;
            sums[0]+=a.nd;
            sums[1]+=b.nd;
            res-=a.st*b.nd;
            res-=a.nd*b.st;
            zle+=a.st*1ll*b.st;
        }
        res+=sums[0]*iles[1];
        res+=sums[1]*iles[0];
        if(typ[real_name[root]]==1)res+=iles[0]*1ll*iles[1]-zle;
        else res+=sums[1-typ[real_name[root]]/2];
        result+=res;
    }
    vector<int> suma[2];
    vector<int> srod;
    void add_srod(int l, int r, int c){
        for(l+=n, r+=n; l<r; l>>=1, r>>=1){
            if(l&1)srod[l++]+=c;
            if(r&1)srod[--r]+=c;
        }
    }
    int get_srod(int v){
        v+=n;
        int ans=0;
        while(v>0){
            ans+=srod[v];
            v/=2;
        }
        return ans;
    }
    int licz_suma(int l, int r, int ktora){
        int ans=0;
        for(l+=n, r+=n; l<r; l>>=1, r>>=1){
            if(l&1)ans+=suma[ktora][l++];
            if(r&1)ans+=suma[ktora][--r];
        }
        return ans;
    }
    void add_suma(int v, int c, int ktora){
        v+=n;
        while(v>0){
            suma[ktora][v]+=c;
            v/=2;
        }
    }
    drzewo(vi V, vector<pii> edges){
        deb(V, edges);
        real_name=V;
        sort(all(real_name));
        n=real_name.size();
        E.resize(n);
        siz.resize(n);
        par.resize(n);
        subtree.resize(n);
        pre.resize(n);
        post.resize(n);
        par[0]=-1;
        for(auto &[u, v] : edges){
            deb(u, v, real_name);
            u=new_name(u);
            v=new_name(v);
            E[u].pb(v);
            E[v].pb(u);
        }
        dfs_cent(0);
        assert(root!=-1);
        deb(root, real_name);
        real_root=real_name[root];
        par[root]=-1;
        ile[0].resize(E[root].size());
        ile[1].resize(E[root].size());
        sum[0].resize(E[root].size());
        sum[1].resize(E[root].size());
        dfs_init(root);
        calc();
        suma[0].resize(n+n);
        suma[1].resize(n+n);
        srod.resize(n+n);
        for(int i=0; i<n; i++){
            if(i==root)continue;
            if(typ[real_name[i]]==1){
                add_srod(pre[i], post[i], 1);
            }
            else{
                add_suma(pre[i], 1, typ[real_name[i]]/2);
            }
        }
    }
    pair<vi, vector<pii> > prep(int v){
        vi vert;
        vector<pii> edg;
        for(int i=pre[v]; i<post[v]; i++){
            int u=order[i];
            vert.pb(real_name[u]);
            for(int w:E[u]){
                edg.pb(mp(real_name[u], real_name[w]));
            }
        }
        return {vert, edg};
    }
    void update_slow(){
        calc();
        deb(res);
    }
    int licz_gora(int v){
        deb(v, typ[real_name[v]]);
        if(v==root)return 0;
        return licz_gora(par[v])+(typ[real_name[v]]==1);
    }
    int licz_gora2(int v){
        return get_srod(pre[v]);
    }
    int licz_dol(int v, int lbl){
        int cnt=0;
        for(int i=pre[v]; i<post[v]; i++){
            if(typ[real_name[order[i]]]==lbl)cnt++;
        }
        return cnt;
    }
    int licz_dol2(int v, int lbl){
        return licz_suma(pre[v], post[v], lbl/2);
    }

    void update_fast(int v, int stary, int nowy){
        v=new_name(v);
        deb(root, v, stary, nowy);
        deb(ile[0], ile[1], sum[0], sum[1]);
        result-=res;
        typ[real_name[v]]=stary;
        
        if(typ[real_name[root]]==1)res-=iles[0]*1ll*iles[1]-zle;
        else res-=sums[1-typ[real_name[root]]/2];
        
        if(v!=root){
            res-=sums[0]*iles[1];
            res-=sums[1]*iles[0];
            int sub=subtree[v];

            iles[0]-=ile[0][sub];
            iles[1]-=ile[1][sub];
            sums[0]-=sum[0][sub];
            sums[1]-=sum[1][sub];
            res+=ile[0][sub]*sum[1][sub];
            res+=ile[1][sub]*sum[0][sub];
            zle-=ile[1][sub]*1ll*ile[0][sub];

            if(stary==1){
                int cnt0=licz_dol2(v, 0);
                int cnt2=licz_dol2(v, 2);
                sum[0][sub]-=cnt0;
                sum[1][sub]-=cnt2;
                add_srod(pre[v], post[v], -1);
            }
            else{
                int cnt=licz_gora2(v);
                //deb(cnt, licz_gora2(v));
                //assert(cnt==licz_gora2(v));
                sum[stary/2][sub]-=cnt;
                ile[stary/2][sub]--;
                add_suma(pre[v], -1, typ[real_name[v]]/2);
            }
            deb(ile[0], ile[1], sum[0], sum[1]);
            deb(res);
            typ[real_name[v]]=nowy;
            
            if(nowy==1){
                int cnt0=licz_dol2(v, 0);
                int cnt2=licz_dol2(v, 2);
                sum[0][sub]+=cnt0;
                sum[1][sub]+=cnt2;
                add_srod(pre[v], post[v], 1);
            }
            else{
                int cnt=licz_gora2(v);
                //deb(cnt, licz_gora2(v));
                //assert(cnt==licz_gora2(v));
                sum[nowy/2][sub]+=cnt;
                ile[nowy/2][sub]++;
                add_suma(pre[v], 1, typ[real_name[v]]/2);
            }

            iles[0]+=ile[0][sub];
            iles[1]+=ile[1][sub];
            sums[0]+=sum[0][sub];
            sums[1]+=sum[1][sub];
            res-=ile[0][sub]*sum[1][sub];
            res-=ile[1][sub]*sum[0][sub];
            zle+=ile[1][sub]*1ll*ile[0][sub];
            
            res+=sums[0]*iles[1];
            res+=sums[1]*iles[0];
        }
        typ[real_name[v]]=nowy;
        if(typ[real_name[root]]==1)res+=iles[0]*1ll*iles[1]-zle;
        else res+=sums[1-typ[real_name[root]]/2];
        result+=res;
        deb(root, v, stary, nowy);
        deb(ile[0], ile[1], sum[0], sum[1]);
        deb(res);
    }
};

vector<drzewo*> drzewa(N);
int rodzic[N];

void stworz(vector<int> vert, vector<pii> edg, int par){
    drzewo* T=new drzewo(vert, edg);
    drzewa[T->real_root]=T;
    deb(T->real_root);
    rodzic[T->real_root]=par;
    for(int u:T->E[T->root]){
        auto a = T->prep(u);
        deb(T->real_root, a.st, a.nd);
        stworz(a.st, a.nd, T->real_root);
    }
}

int n;

void init(int _n, std::vector<int> F, std::vector<int> U, std::vector<int> V,
          int Q) {
    n=_n;
    vector<pii> edges;
    for(int i=0; i<n-1; i++){
        edges.pb(mp(U[i], V[i]));   
    }
    for(int i=0; i<n; i++){
        typ[i]=F[i];
    }
    vi v(n);
    iota(all(v), 0);
    stworz(v, edges, -1);
}

void change(int X, int Y) {
    int stary=typ[X];
    int v=X;
    typ[X]=Y;
    while(X!=-1){
        drzewa[X]->update_fast(v, stary, Y);
        //drzewa[X]->update_slow();
        X=rodzic[X];
    }
}

long long num_tours() {
  return result;
}

Compilation message

joitour.cpp:17:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
joitour.cpp:17:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
joitour.cpp:17:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
joitour.cpp:19:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
joitour.cpp:19:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~
joitour.cpp: In member function 'void drzewo::calc()':
joitour.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i=0; i<E[root].size(); i++){
      |                      ~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1880 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 1 ms 1880 KB Output is correct
14 Correct 1 ms 1880 KB Output is correct
15 Correct 1 ms 1880 KB Output is correct
16 Correct 1 ms 1880 KB Output is correct
17 Correct 1 ms 1880 KB Output is correct
18 Correct 2 ms 1880 KB Output is correct
19 Correct 3 ms 2664 KB Output is correct
20 Correct 2 ms 1880 KB Output is correct
21 Correct 1 ms 1880 KB Output is correct
22 Correct 1 ms 1880 KB Output is correct
23 Correct 1 ms 1880 KB Output is correct
24 Correct 2 ms 2392 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1880 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 1 ms 1880 KB Output is correct
14 Correct 1 ms 1880 KB Output is correct
15 Correct 1 ms 1880 KB Output is correct
16 Correct 1 ms 1880 KB Output is correct
17 Correct 1 ms 1880 KB Output is correct
18 Correct 2 ms 1880 KB Output is correct
19 Correct 3 ms 2664 KB Output is correct
20 Correct 2 ms 1880 KB Output is correct
21 Correct 1 ms 1880 KB Output is correct
22 Correct 1 ms 1880 KB Output is correct
23 Correct 1 ms 1880 KB Output is correct
24 Correct 2 ms 2392 KB Output is correct
25 Correct 20 ms 9560 KB Output is correct
26 Correct 18 ms 8792 KB Output is correct
27 Correct 10 ms 5720 KB Output is correct
28 Correct 19 ms 9660 KB Output is correct
29 Correct 17 ms 9076 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1205 ms 501416 KB Output is correct
3 Correct 1239 ms 501156 KB Output is correct
4 Correct 1203 ms 500972 KB Output is correct
5 Correct 1201 ms 501668 KB Output is correct
6 Correct 840 ms 482356 KB Output is correct
7 Correct 853 ms 482468 KB Output is correct
8 Correct 1145 ms 488892 KB Output is correct
9 Correct 1119 ms 482688 KB Output is correct
10 Correct 1066 ms 462716 KB Output is correct
11 Correct 1018 ms 450128 KB Output is correct
12 Correct 1205 ms 495268 KB Output is correct
13 Correct 1286 ms 495352 KB Output is correct
14 Correct 1178 ms 495196 KB Output is correct
15 Correct 1150 ms 495012 KB Output is correct
16 Correct 1220 ms 520896 KB Output is correct
17 Correct 1 ms 1880 KB Output is correct
18 Correct 1 ms 2132 KB Output is correct
19 Correct 1 ms 1880 KB Output is correct
20 Correct 1 ms 1880 KB Output is correct
21 Correct 980 ms 419924 KB Output is correct
22 Correct 987 ms 417500 KB Output is correct
23 Correct 960 ms 422784 KB Output is correct
24 Correct 1034 ms 424032 KB Output is correct
25 Correct 259 ms 192932 KB Output is correct
26 Correct 248 ms 192932 KB Output is correct
27 Correct 252 ms 192832 KB Output is correct
28 Correct 283 ms 192928 KB Output is correct
29 Correct 872 ms 522172 KB Output is correct
30 Correct 814 ms 522324 KB Output is correct
31 Correct 760 ms 522192 KB Output is correct
32 Correct 765 ms 522340 KB Output is correct
33 Correct 810 ms 486724 KB Output is correct
34 Correct 758 ms 486720 KB Output is correct
35 Correct 754 ms 486760 KB Output is correct
36 Correct 858 ms 486700 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 2 ms 1880 KB Output is correct
7 Correct 3 ms 2648 KB Output is correct
8 Correct 19 ms 9816 KB Output is correct
9 Correct 870 ms 522148 KB Output is correct
10 Correct 849 ms 522148 KB Output is correct
11 Correct 807 ms 522296 KB Output is correct
12 Correct 817 ms 522148 KB Output is correct
13 Correct 648 ms 251572 KB Output is correct
14 Correct 583 ms 251572 KB Output is correct
15 Correct 804 ms 251608 KB Output is correct
16 Correct 766 ms 251488 KB Output is correct
17 Correct 727 ms 251572 KB Output is correct
18 Correct 779 ms 251572 KB Output is correct
19 Correct 1287 ms 522528 KB Output is correct
20 Correct 1195 ms 522276 KB Output is correct
21 Correct 1707 ms 522148 KB Output is correct
22 Correct 1740 ms 522288 KB Output is correct
23 Correct 1644 ms 522336 KB Output is correct
24 Correct 1788 ms 522180 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 23 ms 9048 KB Output is correct
8 Correct 803 ms 486940 KB Output is correct
9 Correct 866 ms 487096 KB Output is correct
10 Correct 833 ms 486812 KB Output is correct
11 Correct 822 ms 486868 KB Output is correct
12 Correct 608 ms 233908 KB Output is correct
13 Correct 720 ms 233908 KB Output is correct
14 Correct 712 ms 233756 KB Output is correct
15 Correct 712 ms 233908 KB Output is correct
16 Correct 743 ms 233912 KB Output is correct
17 Correct 714 ms 233876 KB Output is correct
18 Correct 1205 ms 486724 KB Output is correct
19 Correct 1599 ms 486752 KB Output is correct
20 Correct 1616 ms 486792 KB Output is correct
21 Correct 1606 ms 486860 KB Output is correct
22 Correct 1605 ms 486752 KB Output is correct
23 Correct 1732 ms 486876 KB Output is correct

Subtask #6
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1880 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 1 ms 1880 KB Output is correct
14 Correct 1 ms 1880 KB Output is correct
15 Correct 1 ms 1880 KB Output is correct
16 Correct 1 ms 1880 KB Output is correct
17 Correct 1 ms 1880 KB Output is correct
18 Correct 2 ms 1880 KB Output is correct
19 Correct 3 ms 2664 KB Output is correct
20 Correct 2 ms 1880 KB Output is correct
21 Correct 1 ms 1880 KB Output is correct
22 Correct 1 ms 1880 KB Output is correct
23 Correct 1 ms 1880 KB Output is correct
24 Correct 2 ms 2392 KB Output is correct
25 Correct 20 ms 9560 KB Output is correct
26 Correct 18 ms 8792 KB Output is correct
27 Correct 10 ms 5720 KB Output is correct
28 Correct 19 ms 9660 KB Output is correct
29 Correct 17 ms 9076 KB Output is correct
30 Correct 751 ms 240856 KB Output is correct
31 Correct 736 ms 240856 KB Output is correct
32 Correct 928 ms 240820 KB Output is correct
33 Correct 952 ms 241148 KB Output is correct
34 Correct 942 ms 241272 KB Output is correct
35 Correct 957 ms 240820 KB Output is correct
36 Correct 727 ms 231692 KB Output is correct
37 Correct 761 ms 231764 KB Output is correct
38 Correct 875 ms 234932 KB Output is correct
39 Correct 870 ms 231644 KB Output is correct
40 Correct 805 ms 222644 KB Output is correct
41 Correct 802 ms 216248 KB Output is correct
42 Correct 826 ms 237940 KB Output is correct
43 Correct 873 ms 238028 KB Output is correct
44 Correct 924 ms 238008 KB Output is correct
45 Correct 944 ms 237912 KB Output is correct
46 Correct 934 ms 238004 KB Output is correct
47 Correct 927 ms 238260 KB Output is correct
48 Correct 824 ms 250844 KB Output is correct
49 Correct 773 ms 250844 KB Output is correct
50 Correct 983 ms 250804 KB Output is correct
51 Correct 706 ms 205192 KB Output is correct
52 Correct 784 ms 206292 KB Output is correct
53 Correct 782 ms 205236 KB Output is correct
54 Correct 787 ms 204512 KB Output is correct
55 Correct 851 ms 207028 KB Output is correct
56 Correct 781 ms 205236 KB Output is correct
57 Correct 278 ms 97460 KB Output is correct
58 Correct 292 ms 97460 KB Output is correct
59 Correct 277 ms 97360 KB Output is correct
60 Correct 307 ms 97460 KB Output is correct
61 Correct 271 ms 97460 KB Output is correct
62 Correct 615 ms 251572 KB Output is correct
63 Correct 562 ms 251608 KB Output is correct
64 Correct 798 ms 251544 KB Output is correct
65 Correct 802 ms 251612 KB Output is correct
66 Correct 765 ms 251604 KB Output is correct
67 Correct 843 ms 251616 KB Output is correct
68 Correct 591 ms 233876 KB Output is correct
69 Correct 699 ms 233908 KB Output is correct
70 Correct 761 ms 233908 KB Output is correct
71 Correct 730 ms 233912 KB Output is correct
72 Correct 735 ms 233872 KB Output is correct
73 Correct 733 ms 233684 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 1 ms 1880 KB Output is correct
7 Correct 1 ms 1880 KB Output is correct
8 Correct 1 ms 1880 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 1 ms 1880 KB Output is correct
14 Correct 1 ms 1880 KB Output is correct
15 Correct 1 ms 1880 KB Output is correct
16 Correct 1 ms 1880 KB Output is correct
17 Correct 1 ms 1880 KB Output is correct
18 Correct 2 ms 1880 KB Output is correct
19 Correct 3 ms 2664 KB Output is correct
20 Correct 2 ms 1880 KB Output is correct
21 Correct 1 ms 1880 KB Output is correct
22 Correct 1 ms 1880 KB Output is correct
23 Correct 1 ms 1880 KB Output is correct
24 Correct 2 ms 2392 KB Output is correct
25 Correct 20 ms 9560 KB Output is correct
26 Correct 18 ms 8792 KB Output is correct
27 Correct 10 ms 5720 KB Output is correct
28 Correct 19 ms 9660 KB Output is correct
29 Correct 17 ms 9076 KB Output is correct
30 Correct 1 ms 1880 KB Output is correct
31 Correct 1205 ms 501416 KB Output is correct
32 Correct 1239 ms 501156 KB Output is correct
33 Correct 1203 ms 500972 KB Output is correct
34 Correct 1201 ms 501668 KB Output is correct
35 Correct 840 ms 482356 KB Output is correct
36 Correct 853 ms 482468 KB Output is correct
37 Correct 1145 ms 488892 KB Output is correct
38 Correct 1119 ms 482688 KB Output is correct
39 Correct 1066 ms 462716 KB Output is correct
40 Correct 1018 ms 450128 KB Output is correct
41 Correct 1205 ms 495268 KB Output is correct
42 Correct 1286 ms 495352 KB Output is correct
43 Correct 1178 ms 495196 KB Output is correct
44 Correct 1150 ms 495012 KB Output is correct
45 Correct 1220 ms 520896 KB Output is correct
46 Correct 1 ms 1880 KB Output is correct
47 Correct 1 ms 2132 KB Output is correct
48 Correct 1 ms 1880 KB Output is correct
49 Correct 1 ms 1880 KB Output is correct
50 Correct 980 ms 419924 KB Output is correct
51 Correct 987 ms 417500 KB Output is correct
52 Correct 960 ms 422784 KB Output is correct
53 Correct 1034 ms 424032 KB Output is correct
54 Correct 259 ms 192932 KB Output is correct
55 Correct 248 ms 192932 KB Output is correct
56 Correct 252 ms 192832 KB Output is correct
57 Correct 283 ms 192928 KB Output is correct
58 Correct 872 ms 522172 KB Output is correct
59 Correct 814 ms 522324 KB Output is correct
60 Correct 760 ms 522192 KB Output is correct
61 Correct 765 ms 522340 KB Output is correct
62 Correct 810 ms 486724 KB Output is correct
63 Correct 758 ms 486720 KB Output is correct
64 Correct 754 ms 486760 KB Output is correct
65 Correct 858 ms 486700 KB Output is correct
66 Correct 1 ms 1880 KB Output is correct
67 Correct 1 ms 1880 KB Output is correct
68 Correct 1 ms 1880 KB Output is correct
69 Correct 1 ms 1880 KB Output is correct
70 Correct 1 ms 1880 KB Output is correct
71 Correct 2 ms 1880 KB Output is correct
72 Correct 3 ms 2648 KB Output is correct
73 Correct 19 ms 9816 KB Output is correct
74 Correct 870 ms 522148 KB Output is correct
75 Correct 849 ms 522148 KB Output is correct
76 Correct 807 ms 522296 KB Output is correct
77 Correct 817 ms 522148 KB Output is correct
78 Correct 648 ms 251572 KB Output is correct
79 Correct 583 ms 251572 KB Output is correct
80 Correct 804 ms 251608 KB Output is correct
81 Correct 766 ms 251488 KB Output is correct
82 Correct 727 ms 251572 KB Output is correct
83 Correct 779 ms 251572 KB Output is correct
84 Correct 1287 ms 522528 KB Output is correct
85 Correct 1195 ms 522276 KB Output is correct
86 Correct 1707 ms 522148 KB Output is correct
87 Correct 1740 ms 522288 KB Output is correct
88 Correct 1644 ms 522336 KB Output is correct
89 Correct 1788 ms 522180 KB Output is correct
90 Correct 1 ms 1880 KB Output is correct
91 Correct 1 ms 1880 KB Output is correct
92 Correct 1 ms 1880 KB Output is correct
93 Correct 1 ms 1880 KB Output is correct
94 Correct 1 ms 1880 KB Output is correct
95 Correct 2 ms 2392 KB Output is correct
96 Correct 23 ms 9048 KB Output is correct
97 Correct 803 ms 486940 KB Output is correct
98 Correct 866 ms 487096 KB Output is correct
99 Correct 833 ms 486812 KB Output is correct
100 Correct 822 ms 486868 KB Output is correct
101 Correct 608 ms 233908 KB Output is correct
102 Correct 720 ms 233908 KB Output is correct
103 Correct 712 ms 233756 KB Output is correct
104 Correct 712 ms 233908 KB Output is correct
105 Correct 743 ms 233912 KB Output is correct
106 Correct 714 ms 233876 KB Output is correct
107 Correct 1205 ms 486724 KB Output is correct
108 Correct 1599 ms 486752 KB Output is correct
109 Correct 1616 ms 486792 KB Output is correct
110 Correct 1606 ms 486860 KB Output is correct
111 Correct 1605 ms 486752 KB Output is correct
112 Correct 1732 ms 486876 KB Output is correct
113 Correct 751 ms 240856 KB Output is correct
114 Correct 736 ms 240856 KB Output is correct
115 Correct 928 ms 240820 KB Output is correct
116 Correct 952 ms 241148 KB Output is correct
117 Correct 942 ms 241272 KB Output is correct
118 Correct 957 ms 240820 KB Output is correct
119 Correct 727 ms 231692 KB Output is correct
120 Correct 761 ms 231764 KB Output is correct
121 Correct 875 ms 234932 KB Output is correct
122 Correct 870 ms 231644 KB Output is correct
123 Correct 805 ms 222644 KB Output is correct
124 Correct 802 ms 216248 KB Output is correct
125 Correct 826 ms 237940 KB Output is correct
126 Correct 873 ms 238028 KB Output is correct
127 Correct 924 ms 238008 KB Output is correct
128 Correct 944 ms 237912 KB Output is correct
129 Correct 934 ms 238004 KB Output is correct
130 Correct 927 ms 238260 KB Output is correct
131 Correct 824 ms 250844 KB Output is correct
132 Correct 773 ms 250844 KB Output is correct
133 Correct 983 ms 250804 KB Output is correct
134 Correct 706 ms 205192 KB Output is correct
135 Correct 784 ms 206292 KB Output is correct
136 Correct 782 ms 205236 KB Output is correct
137 Correct 787 ms 204512 KB Output is correct
138 Correct 851 ms 207028 KB Output is correct
139 Correct 781 ms 205236 KB Output is correct
140 Correct 278 ms 97460 KB Output is correct
141 Correct 292 ms 97460 KB Output is correct
142 Correct 277 ms 97360 KB Output is correct
143 Correct 307 ms 97460 KB Output is correct
144 Correct 271 ms 97460 KB Output is correct
145 Correct 615 ms 251572 KB Output is correct
146 Correct 562 ms 251608 KB Output is correct
147 Correct 798 ms 251544 KB Output is correct
148 Correct 802 ms 251612 KB Output is correct
149 Correct 765 ms 251604 KB Output is correct
150 Correct 843 ms 251616 KB Output is correct
151 Correct 591 ms 233876 KB Output is correct
152 Correct 699 ms 233908 KB Output is correct
153 Correct 761 ms 233908 KB Output is correct
154 Correct 730 ms 233912 KB Output is correct
155 Correct 735 ms 233872 KB Output is correct
156 Correct 733 ms 233684 KB Output is correct
157 Correct 1623 ms 500900 KB Output is correct
158 Correct 1589 ms 501392 KB Output is correct
159 Correct 2047 ms 501076 KB Output is correct
160 Correct 2168 ms 500928 KB Output is correct
161 Correct 2021 ms 501668 KB Output is correct
162 Correct 2071 ms 501424 KB Output is correct
163 Correct 1694 ms 482332 KB Output is correct
164 Correct 1538 ms 482644 KB Output is correct
165 Correct 1929 ms 489124 KB Output is correct
166 Correct 1982 ms 482656 KB Output is correct
167 Correct 1881 ms 462756 KB Output is correct
168 Correct 1811 ms 446108 KB Output is correct
169 Correct 1668 ms 495152 KB Output is correct
170 Correct 1971 ms 495100 KB Output is correct
171 Correct 2050 ms 495084 KB Output is correct
172 Correct 2033 ms 494920 KB Output is correct
173 Correct 1988 ms 495196 KB Output is correct
174 Correct 2061 ms 495192 KB Output is correct
175 Correct 1733 ms 521004 KB Output is correct
176 Correct 1755 ms 520752 KB Output is correct
177 Correct 2270 ms 521816 KB Output is correct
178 Correct 1505 ms 422120 KB Output is correct
179 Correct 1707 ms 420856 KB Output is correct
180 Correct 1772 ms 432320 KB Output is correct
181 Correct 1788 ms 418616 KB Output is correct
182 Correct 1724 ms 422724 KB Output is correct
183 Correct 1742 ms 417956 KB Output is correct
184 Correct 550 ms 192956 KB Output is correct
185 Correct 634 ms 192872 KB Output is correct
186 Correct 586 ms 192816 KB Output is correct
187 Correct 621 ms 193044 KB Output is correct
188 Correct 614 ms 192940 KB Output is correct