oj.uz

Submission #968347

# Submission time Handle Problem Language Result Execution time Memory
968347 2024-04-23T10:30:10 Z shadow_sami Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 3903 ms 386504 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
// typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"
 
// ==========================(debug)============================================================================================== //
 
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif
 
void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
 
// ==========================(debug)============================================================================================== //
 
ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;
 
// ==========================(MOD)=============================================================================================== //
 
ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }
 
// ==========================(MOD)=============================================================================================== //
 
bool f = false;
const ll mxn = 20;
vector<pi> adj[mx];
ll aa[mx];
ll bb[mx];
ll c[mx];
ll val[mx];
ll to[mx][mxn];
bool mark[mx];
ll sz[mx];
ll st[mx][mxn];
ll en[mx][mxn];
ll id[mx][mxn];
ll id2[mx][mxn];
ll sr,de;
ll timer[mxn];
 
typedef struct SEGMENT_TREE{
	vi arr;
	vi laz;
	vi mid;
	ll range;
	void init(ll k){
		range = 4 * k;
		arr.resize(range);
		mid.resize(range);
		laz.resize(range);
		fip(0,range)
			laz[i] = arr[i] = 0;
		return;
	}
	void prop(ll ptr,ll l,ll r){
		if(laz[ptr]){
			arr[ptr] += laz[ptr];
			if(l!=r){
				laz[2*ptr] += laz[ptr];
				laz[2*ptr+1] += laz[ptr];
			}
			laz[ptr] = 0;
		}
		return;
	}
	ll build(ll ptr,ll l,ll r){
		if(l==r){
			arr[ptr] = 0;
			return arr[ptr];
		}
		mid[ptr] = l + (r-l) / 2;
		build(2*ptr,l,mid[ptr]);
		build(2*ptr+1,mid[ptr]+1,r);
		arr[ptr] = max(arr[2*ptr],arr[2*ptr+1]);
		return arr[ptr];
	}
	ll update(ll ptr,ll l,ll r,ll st,ll en,ll val){
		prop(ptr,l,r);
		if(l>en || r<st)
			return arr[ptr];
		if(l>=st && r<=en){
			laz[ptr] += val;
			prop(ptr,l,r);
			return arr[ptr];
		}
		update(2*ptr,l,mid[ptr],st,en,val);
		update(2*ptr+1,mid[ptr]+1,r,st,en,val);
		arr[ptr] = max(arr[2*ptr],arr[2*ptr+1]);
		return arr[ptr];
	}
	ll query(ll ptr,ll l,ll r,ll st,ll en){
		prop(ptr,l,r);
		if(l>en || r<st)
			return -1e18;
		if(l>=st && r<=en)
			return arr[ptr];		
		return max(query(2*ptr,l,mid[ptr],st,en),query(2*ptr+1,mid[ptr]+1,r,st,en));
	}
}SGT;
 
SGT sg[mxn];
priority_queue<pi> les[mx];
priority_queue<pi> sol,ptt;
ll dp[mx][mxn];
ll dp2[mx];

void dfs(ll u,ll par){
	sz[u] = 1;
	fx(adj[u]){
		if(x.ff==par || mark[x.ff])continue;
		dfs(x.ff,u);
		sz[u] += sz[x.ff];
	}
	return;
}

ll get(ll u,ll par,ll k){
	fx(adj[u]){
		if(x.ff==par || mark[x.ff])continue;
		if(sz[x.ff]*2>k)
			return get(x.ff,u,k);
	}
	return u;
}

void ds(ll u,ll par,ll k,ll d,ll p,ll pp){	
	to[u][k] = par;
	id[u][k] = p;
	id2[u][k] = pp;
	st[u][k] = timer[k]++;
	sg[k].update(1,0,n-1,st[u][k],st[u][k],d);
	fx(adj[u]){
		if(x.ff==par || mark[x.ff])continue;
		ds(x.ff,u,k,d+c[x.ss],p,pp);		
	}
	en[u][k] = timer[k]-1;
	return;
}
pi pt,pt2;

ll calc(ll d,ll k){
	while(les[d].size()&& dp[les[d].top().ss][k]!=les[d].top().ff)
		les[d].pop();
	if(!les[d].size())
		return 0;
	// ptt = les[d];
	// while(ptt.size()){
	// 	debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	pt = les[d].top();
	// debug(pt);
	pt2 = {0,0};
	while(les[d].size() && ((dp[les[d].top().ss][k]!=les[d].top().ff) || (les[d].top()==pt))){
		// debug(les[d].top());
		// debug(pt);
		// debug((dp[les[d].top().ss][k]));
		// cerr<<nli;
		les[d].pop();	
	}
	// debug((ll)les[d].size());
	// ptt = les[d];
	// while(ptt.size()){
	// 	debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	if(les[d].size())
		pt2 = les[d].top();
	// debug(pt2);
	les[d].push(pt);
	return pt.ff+pt2.ff;
}

void divide(ll u,ll d){
	dfs(u,-1);	
	u = get(u,-1,sz[u]);	
	// debug(u);	
	mark[u] = 1;
	val[u] = d;
	fx(adj[u])
		if(!mark[x.ff]){
			ds(x.ff,u,d,c[x.ss],u,x.ff);
			les[u].push({dp[x.ff][d] = sg[d].query(1,0,n-1,st[x.ff][d],en[x.ff][d]),x.ff});
		}
	// fip(1,n+1)
	// 	cerr<<st[i][d]<<" ";
	// cerr<<nli;
	// fip(1,n+1)
	// 	cerr<<en[i][d]<<" ";
	// cerr<<nli;
	// ptt = les[u];
	// while(ptt.size()){
	// 	debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	sol.push({dp2[u] = calc(u,d),u});
	// ptt = sol;
	// while(ptt.size()){
	// 	// debug(ptt.top());
	// 	ptt.pop();
	// }
	// cerr<<nli;
	// // cerr<<"non"<<nli;
	// // 	ptt = les[1];
	// // 	while(ptt.size()){
	// // 		debug(ptt.top());
	// // 		ptt.pop();
	// // 	}
	// // 	cerr<<nli;
	fx(adj[u])
		if(!mark[x.ff])
			divide(x.ff,d+1);	
	return;
}

void update(ll a,ll b){
	// debug(a);
	// debug(b);
	fjp(0,mxn){
		if(val[a]<j || val[b]<j)
			break;
		if(to[a][j]==b)
			swap(a,b);
		// debug(id[b][j]);
		// debug(de-c[sr]);
		// debug(id2[b][j]);
		// debug(st[b][j]);
		// debug(en[b][j]);
		// fip(1,n+1)
		// 	cerr<<sg[j].query(1,0,n-1,st[i][j],st[i][j])<<" ";
		// cerr<<nli;
		sg[j].update(1,0,n-1,st[b][j],en[b][j],de-c[sr]);
		// ptt = les[id[b][j]];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		les[id[b][j]].push({dp[id2[b][j]][j] = sg[j].query(1,0,n-1,st[id2[b][j]][j],en[id2[b][j]][j]),id2[b][j]});		
		// ptt = les[id[b][j]];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		// cerr<<"calc"<<nli;
		sol.push({dp2[id[b][j]] = calc(id[b][j],j),id[b][j]});
		// cerr<<"calc"<<nli;
		// ptt = les[id[b][j]];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
	}
	while(sol.size() && dp2[sol.top().ss]!=sol.top().ff)
		sol.pop();

	return;
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE
 
        cin>>n>>m>>tp;
        fip(0,n-1){
        	cin>>sr>>de>>tptp;
        	adj[sr].push_back({de,i});
        	adj[de].push_back({sr,i});
        	c[i] = tptp;
        	aa[i] = sr;
        	bb[i] = de;
    	}
    	res = 0;
    	fip(0,mxn){
    		sg[i].init(n);
			sg[i].build(1,0,n-1);
    	}
		divide(1,0);
		// ptt = sol;
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		// cerr<<"non"<<nli;
		// ptt = les[1];
		// while(ptt.size()){
		// 	debug(ptt.top());
		// 	ptt.pop();
		// }
		// cerr<<nli;
		// cerr<<nli;
		// cerr<<"start"<<nli;
    	while(m--){
    		cin>>sr>>de;
    		sr += res;
    		sr %= (n-1);
    		de += res;
    		de %= (tp);    		
    		ans = 0;
    		// debug(sr);
    		// debug(de);

    		update(aa[sr],bb[sr]);
    		ans = sol.top().ff;
    		c[sr] = de;
    		cout<<ans<<nli;    		
    		res = ans;
    	}
        
    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49244 KB Output is correct
2 Correct 11 ms 49244 KB Output is correct
3 Correct 10 ms 49244 KB Output is correct
4 Correct 11 ms 49348 KB Output is correct
5 Correct 11 ms 49244 KB Output is correct
6 Correct 11 ms 49348 KB Output is correct
7 Correct 12 ms 49496 KB Output is correct
8 Correct 10 ms 49500 KB Output is correct
9 Correct 10 ms 49320 KB Output is correct
10 Correct 10 ms 49496 KB Output is correct
11 Correct 10 ms 49500 KB Output is correct
12 Correct 10 ms 49520 KB Output is correct
13 Correct 12 ms 49596 KB Output is correct
14 Correct 10 ms 49608 KB Output is correct
15 Correct 10 ms 49500 KB Output is correct
16 Correct 11 ms 49500 KB Output is correct
17 Correct 14 ms 49592 KB Output is correct
18 Correct 10 ms 49624 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49244 KB Output is correct
2 Correct 11 ms 49244 KB Output is correct
3 Correct 10 ms 49244 KB Output is correct
4 Correct 11 ms 49348 KB Output is correct
5 Correct 11 ms 49244 KB Output is correct
6 Correct 11 ms 49348 KB Output is correct
7 Correct 12 ms 49496 KB Output is correct
8 Correct 10 ms 49500 KB Output is correct
9 Correct 10 ms 49320 KB Output is correct
10 Correct 10 ms 49496 KB Output is correct
11 Correct 10 ms 49500 KB Output is correct
12 Correct 10 ms 49520 KB Output is correct
13 Correct 12 ms 49596 KB Output is correct
14 Correct 10 ms 49608 KB Output is correct
15 Correct 10 ms 49500 KB Output is correct
16 Correct 11 ms 49500 KB Output is correct
17 Correct 14 ms 49592 KB Output is correct
18 Correct 10 ms 49624 KB Output is correct
19 Correct 25 ms 51836 KB Output is correct
20 Correct 31 ms 51856 KB Output is correct
21 Correct 29 ms 51924 KB Output is correct
22 Correct 31 ms 52180 KB Output is correct
23 Correct 45 ms 66804 KB Output is correct
24 Correct 58 ms 67024 KB Output is correct
25 Correct 59 ms 67528 KB Output is correct
26 Correct 64 ms 68004 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 49436 KB Output is correct
2 Correct 11 ms 49244 KB Output is correct
3 Correct 11 ms 49244 KB Output is correct
4 Correct 21 ms 49708 KB Output is correct
5 Correct 60 ms 50896 KB Output is correct
6 Correct 9 ms 49240 KB Output is correct
7 Correct 10 ms 50268 KB Output is correct
8 Correct 10 ms 50268 KB Output is correct
9 Correct 11 ms 50520 KB Output is correct
10 Correct 23 ms 51024 KB Output is correct
11 Correct 73 ms 52608 KB Output is correct
12 Correct 18 ms 66396 KB Output is correct
13 Correct 18 ms 66396 KB Output is correct
14 Correct 20 ms 66396 KB Output is correct
15 Correct 34 ms 66908 KB Output is correct
16 Correct 92 ms 68680 KB Output is correct
17 Correct 168 ms 338648 KB Output is correct
18 Correct 159 ms 338708 KB Output is correct
19 Correct 164 ms 338692 KB Output is correct
20 Correct 190 ms 338704 KB Output is correct
21 Correct 301 ms 342352 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 51544 KB Output is correct
2 Correct 36 ms 52212 KB Output is correct
3 Correct 140 ms 54088 KB Output is correct
4 Correct 286 ms 56988 KB Output is correct
5 Correct 51 ms 81164 KB Output is correct
6 Correct 94 ms 82128 KB Output is correct
7 Correct 288 ms 87232 KB Output is correct
8 Correct 507 ms 92196 KB Output is correct
9 Correct 236 ms 199716 KB Output is correct
10 Correct 345 ms 201216 KB Output is correct
11 Correct 666 ms 204716 KB Output is correct
12 Correct 1090 ms 210100 KB Output is correct
13 Correct 484 ms 342300 KB Output is correct
14 Correct 588 ms 345080 KB Output is correct
15 Correct 1012 ms 350596 KB Output is correct
16 Correct 1574 ms 351804 KB Output is correct
17 Correct 2779 ms 386504 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2238 ms 365520 KB Output is correct
2 Correct 2243 ms 367212 KB Output is correct
3 Correct 2211 ms 367772 KB Output is correct
4 Correct 2297 ms 366444 KB Output is correct
5 Correct 2179 ms 367508 KB Output is correct
6 Correct 2114 ms 382164 KB Output is correct
7 Correct 3165 ms 381164 KB Output is correct
8 Correct 3231 ms 381248 KB Output is correct
9 Correct 3138 ms 382820 KB Output is correct
10 Correct 3234 ms 382688 KB Output is correct
11 Correct 3173 ms 382516 KB Output is correct
12 Correct 3140 ms 376644 KB Output is correct
13 Correct 3903 ms 385764 KB Output is correct
14 Correct 3654 ms 384656 KB Output is correct
15 Correct 3724 ms 379648 KB Output is correct
16 Correct 3393 ms 385772 KB Output is correct
17 Correct 3452 ms 384984 KB Output is correct
18 Correct 2825 ms 380612 KB Output is correct
19 Correct 3501 ms 385660 KB Output is correct
20 Correct 3517 ms 385764 KB Output is correct
21 Correct 3503 ms 385996 KB Output is correct
22 Correct 3444 ms 384016 KB Output is correct
23 Correct 3474 ms 384944 KB Output is correct
24 Correct 2867 ms 379060 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49244 KB Output is correct
2 Correct 11 ms 49244 KB Output is correct
3 Correct 10 ms 49244 KB Output is correct
4 Correct 11 ms 49348 KB Output is correct
5 Correct 11 ms 49244 KB Output is correct
6 Correct 11 ms 49348 KB Output is correct
7 Correct 12 ms 49496 KB Output is correct
8 Correct 10 ms 49500 KB Output is correct
9 Correct 10 ms 49320 KB Output is correct
10 Correct 10 ms 49496 KB Output is correct
11 Correct 10 ms 49500 KB Output is correct
12 Correct 10 ms 49520 KB Output is correct
13 Correct 12 ms 49596 KB Output is correct
14 Correct 10 ms 49608 KB Output is correct
15 Correct 10 ms 49500 KB Output is correct
16 Correct 11 ms 49500 KB Output is correct
17 Correct 14 ms 49592 KB Output is correct
18 Correct 10 ms 49624 KB Output is correct
19 Correct 25 ms 51836 KB Output is correct
20 Correct 31 ms 51856 KB Output is correct
21 Correct 29 ms 51924 KB Output is correct
22 Correct 31 ms 52180 KB Output is correct
23 Correct 45 ms 66804 KB Output is correct
24 Correct 58 ms 67024 KB Output is correct
25 Correct 59 ms 67528 KB Output is correct
26 Correct 64 ms 68004 KB Output is correct
27 Correct 9 ms 49436 KB Output is correct
28 Correct 11 ms 49244 KB Output is correct
29 Correct 11 ms 49244 KB Output is correct
30 Correct 21 ms 49708 KB Output is correct
31 Correct 60 ms 50896 KB Output is correct
32 Correct 9 ms 49240 KB Output is correct
33 Correct 10 ms 50268 KB Output is correct
34 Correct 10 ms 50268 KB Output is correct
35 Correct 11 ms 50520 KB Output is correct
36 Correct 23 ms 51024 KB Output is correct
37 Correct 73 ms 52608 KB Output is correct
38 Correct 18 ms 66396 KB Output is correct
39 Correct 18 ms 66396 KB Output is correct
40 Correct 20 ms 66396 KB Output is correct
41 Correct 34 ms 66908 KB Output is correct
42 Correct 92 ms 68680 KB Output is correct
43 Correct 168 ms 338648 KB Output is correct
44 Correct 159 ms 338708 KB Output is correct
45 Correct 164 ms 338692 KB Output is correct
46 Correct 190 ms 338704 KB Output is correct
47 Correct 301 ms 342352 KB Output is correct
48 Correct 14 ms 51544 KB Output is correct
49 Correct 36 ms 52212 KB Output is correct
50 Correct 140 ms 54088 KB Output is correct
51 Correct 286 ms 56988 KB Output is correct
52 Correct 51 ms 81164 KB Output is correct
53 Correct 94 ms 82128 KB Output is correct
54 Correct 288 ms 87232 KB Output is correct
55 Correct 507 ms 92196 KB Output is correct
56 Correct 236 ms 199716 KB Output is correct
57 Correct 345 ms 201216 KB Output is correct
58 Correct 666 ms 204716 KB Output is correct
59 Correct 1090 ms 210100 KB Output is correct
60 Correct 484 ms 342300 KB Output is correct
61 Correct 588 ms 345080 KB Output is correct
62 Correct 1012 ms 350596 KB Output is correct
63 Correct 1574 ms 351804 KB Output is correct
64 Correct 2779 ms 386504 KB Output is correct
65 Correct 2238 ms 365520 KB Output is correct
66 Correct 2243 ms 367212 KB Output is correct
67 Correct 2211 ms 367772 KB Output is correct
68 Correct 2297 ms 366444 KB Output is correct
69 Correct 2179 ms 367508 KB Output is correct
70 Correct 2114 ms 382164 KB Output is correct
71 Correct 3165 ms 381164 KB Output is correct
72 Correct 3231 ms 381248 KB Output is correct
73 Correct 3138 ms 382820 KB Output is correct
74 Correct 3234 ms 382688 KB Output is correct
75 Correct 3173 ms 382516 KB Output is correct
76 Correct 3140 ms 376644 KB Output is correct
77 Correct 3903 ms 385764 KB Output is correct
78 Correct 3654 ms 384656 KB Output is correct
79 Correct 3724 ms 379648 KB Output is correct
80 Correct 3393 ms 385772 KB Output is correct
81 Correct 3452 ms 384984 KB Output is correct
82 Correct 2825 ms 380612 KB Output is correct
83 Correct 3501 ms 385660 KB Output is correct
84 Correct 3517 ms 385764 KB Output is correct
85 Correct 3503 ms 385996 KB Output is correct
86 Correct 3444 ms 384016 KB Output is correct
87 Correct 3474 ms 384944 KB Output is correct
88 Correct 2867 ms 379060 KB Output is correct
89 Correct 2342 ms 361708 KB Output is correct
90 Correct 2792 ms 379024 KB Output is correct
91 Correct 3247 ms 379376 KB Output is correct
92 Correct 3231 ms 379456 KB Output is correct
93 Correct 3278 ms 383132 KB Output is correct
94 Correct 3431 ms 381464 KB Output is correct
95 Correct 3514 ms 381656 KB Output is correct
96 Correct 3535 ms 381328 KB Output is correct
97 Correct 3521 ms 381660 KB Output is correct
98 Correct 3590 ms 383384 KB Output is correct
99 Correct 3401 ms 380244 KB Output is correct
100 Correct 3395 ms 382288 KB Output is correct