oj.uz

Submission #155287

# Submission time Handle Problem Language Result Execution time Memory
155287 2019-09-27T13:03:51 Z ryansee Rope (JOI17_rope) C++14
80 / 100
 2500 ms 168776 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }

#define ll /*long long*/ int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF INF// ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (1000006)
ll n, m, A[MAXN]; ll N;
vector<pi> v;
ll ans[MAXN];
vector<ll> cnt;
struct node {
	int s,e,m;
	ll v;
	node *l,*r;
	node (ll _S, ll _E) {
		s=_S,e=_E,m=(s+e)>>1;
		v=0;
		if(s^e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void update(ll x,ll nval) {
		if(s==e) {
			v+=nval;
			return;
		}
		if(x>m) r->update(x,nval); else l->update(x,nval);
		v=max(l->v,r->v);
	}
	ll rmq() {
		return v;
	}
} *seg;
void solve() {
	ll n=v.size();
	vector<ll> mp(m+1, 0);
	vector<vector<ll>> adj(m+1, vector<ll>());
	FOR(i,0,n-1) if(v[i].s!=-1) {
		adj[v[i].f].eb(v[i].s);
		adj[v[i].s].eb(v[i].f);
	}
	FOR(i,1,m) {
		// ll n=v.size();
		ll add = 0;
		for(auto j:adj[i]) seg->update(j, -1);
		seg->update(i, -cnt[i]);
		add = N-cnt[i]-seg->rmq();
		ans[i]=min(ans[i], add);
		seg->update(i,cnt[i]);
		for(auto j:adj[i]) seg->update(j, 1);
	}
}
int main()
{
	FAST
	cin>>n>>m;N=n;
	if(m==1) {
		cout<<0; return 0;
	}
	FOR(i,1,n) cin>>A[i]; cnt.resize(m+1, 0); for(ll i=1;i<=n;++i) cnt[A[i]] ++; seg=new node(1, m); FOR(i,1,n) seg->update(A[i],1);
	for(ll i=1;i<=n;i+=2) v.eb(A[i], (i+1>n?-1:A[i+1]));
	fill(ans, ans+MAXN, LLINF);
	solve();
	v.clear();
	v.eb(A[1], -1);
	for(ll i=2;i<=n;i+=2) v.eb(A[i], (i+1>n?-1:A[i+1]));
	solve();
	for(ll i=1;i<=m;++i) cout<<ans[i]<<'\n';
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:24:25: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
                         ^
rope.cpp:86:2: note: in expansion of macro 'FOR'
  FOR(i,1,n) cin>>A[i]; cnt.resize(m+1, 0); for(ll i=1;i<=n;++i) cnt[A[i]] ++; seg=new node(1, m); FOR(i,1,n) seg->update(A[i],1);
  ^~~
rope.cpp:86:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,1,n) cin>>A[i]; cnt.resize(m+1, 0); for(ll i=1;i<=n;++i) cnt[A[i]] ++; seg=new node(1, m); FOR(i,1,n) seg->update(A[i],1);
                        ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 4220 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 5 ms 4240 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 5 ms 4216 KB Output is correct
13 Correct 6 ms 4216 KB Output is correct
14 Correct 5 ms 4216 KB Output is correct
15 Correct 5 ms 4216 KB Output is correct
16 Correct 5 ms 4216 KB Output is correct
17 Correct 6 ms 4304 KB Output is correct
18 Correct 6 ms 4344 KB Output is correct
19 Correct 6 ms 4244 KB Output is correct
20 Correct 5 ms 4216 KB Output is correct
21 Correct 5 ms 4244 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 5 ms 4216 KB Output is correct
24 Correct 5 ms 4216 KB Output is correct
25 Correct 5 ms 4216 KB Output is correct
26 Correct 2 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 4220 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 5 ms 4240 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 5 ms 4216 KB Output is correct
13 Correct 6 ms 4216 KB Output is correct
14 Correct 5 ms 4216 KB Output is correct
15 Correct 5 ms 4216 KB Output is correct
16 Correct 5 ms 4216 KB Output is correct
17 Correct 6 ms 4304 KB Output is correct
18 Correct 6 ms 4344 KB Output is correct
19 Correct 6 ms 4244 KB Output is correct
20 Correct 5 ms 4216 KB Output is correct
21 Correct 5 ms 4244 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 5 ms 4216 KB Output is correct
24 Correct 5 ms 4216 KB Output is correct
25 Correct 5 ms 4216 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 30 ms 5892 KB Output is correct
28 Correct 24 ms 5836 KB Output is correct
29 Correct 29 ms 5748 KB Output is correct
30 Correct 26 ms 5876 KB Output is correct
31 Correct 32 ms 5868 KB Output is correct
32 Correct 64 ms 5800 KB Output is correct
33 Correct 29 ms 5876 KB Output is correct
34 Correct 27 ms 5900 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 4220 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 5 ms 4240 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 5 ms 4216 KB Output is correct
13 Correct 6 ms 4216 KB Output is correct
14 Correct 5 ms 4216 KB Output is correct
15 Correct 5 ms 4216 KB Output is correct
16 Correct 5 ms 4216 KB Output is correct
17 Correct 6 ms 4304 KB Output is correct
18 Correct 6 ms 4344 KB Output is correct
19 Correct 6 ms 4244 KB Output is correct
20 Correct 5 ms 4216 KB Output is correct
21 Correct 5 ms 4244 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 5 ms 4216 KB Output is correct
24 Correct 5 ms 4216 KB Output is correct
25 Correct 5 ms 4216 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 30 ms 5892 KB Output is correct
28 Correct 24 ms 5836 KB Output is correct
29 Correct 29 ms 5748 KB Output is correct
30 Correct 26 ms 5876 KB Output is correct
31 Correct 32 ms 5868 KB Output is correct
32 Correct 64 ms 5800 KB Output is correct
33 Correct 29 ms 5876 KB Output is correct
34 Correct 27 ms 5900 KB Output is correct
35 Correct 70 ms 5856 KB Output is correct
36 Correct 65 ms 5972 KB Output is correct
37 Correct 62 ms 5836 KB Output is correct
38 Correct 61 ms 5844 KB Output is correct
39 Correct 64 ms 5960 KB Output is correct
40 Correct 49 ms 5872 KB Output is correct
41 Correct 51 ms 5904 KB Output is correct
42 Correct 46 ms 5896 KB Output is correct
43 Correct 45 ms 5912 KB Output is correct
44 Correct 50 ms 5872 KB Output is correct
45 Correct 49 ms 5868 KB Output is correct
46 Correct 45 ms 5892 KB Output is correct
47 Correct 44 ms 5876 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 4220 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 5 ms 4240 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 5 ms 4216 KB Output is correct
13 Correct 6 ms 4216 KB Output is correct
14 Correct 5 ms 4216 KB Output is correct
15 Correct 5 ms 4216 KB Output is correct
16 Correct 5 ms 4216 KB Output is correct
17 Correct 6 ms 4304 KB Output is correct
18 Correct 6 ms 4344 KB Output is correct
19 Correct 6 ms 4244 KB Output is correct
20 Correct 5 ms 4216 KB Output is correct
21 Correct 5 ms 4244 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 5 ms 4216 KB Output is correct
24 Correct 5 ms 4216 KB Output is correct
25 Correct 5 ms 4216 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 30 ms 5892 KB Output is correct
28 Correct 24 ms 5836 KB Output is correct
29 Correct 29 ms 5748 KB Output is correct
30 Correct 26 ms 5876 KB Output is correct
31 Correct 32 ms 5868 KB Output is correct
32 Correct 64 ms 5800 KB Output is correct
33 Correct 29 ms 5876 KB Output is correct
34 Correct 27 ms 5900 KB Output is correct
35 Correct 70 ms 5856 KB Output is correct
36 Correct 65 ms 5972 KB Output is correct
37 Correct 62 ms 5836 KB Output is correct
38 Correct 61 ms 5844 KB Output is correct
39 Correct 64 ms 5960 KB Output is correct
40 Correct 49 ms 5872 KB Output is correct
41 Correct 51 ms 5904 KB Output is correct
42 Correct 46 ms 5896 KB Output is correct
43 Correct 45 ms 5912 KB Output is correct
44 Correct 50 ms 5872 KB Output is correct
45 Correct 49 ms 5868 KB Output is correct
46 Correct 45 ms 5892 KB Output is correct
47 Correct 44 ms 5876 KB Output is correct
48 Correct 805 ms 19172 KB Output is correct
49 Correct 805 ms 19184 KB Output is correct
50 Correct 804 ms 19168 KB Output is correct
51 Correct 689 ms 18984 KB Output is correct
52 Correct 617 ms 17924 KB Output is correct
53 Correct 687 ms 18520 KB Output is correct
54 Correct 652 ms 17376 KB Output is correct
55 Correct 657 ms 17200 KB Output is correct
56 Correct 627 ms 16864 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 5 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4216 KB Output is correct
7 Correct 5 ms 4220 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 5 ms 4240 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 5 ms 4216 KB Output is correct
13 Correct 6 ms 4216 KB Output is correct
14 Correct 5 ms 4216 KB Output is correct
15 Correct 5 ms 4216 KB Output is correct
16 Correct 5 ms 4216 KB Output is correct
17 Correct 6 ms 4304 KB Output is correct
18 Correct 6 ms 4344 KB Output is correct
19 Correct 6 ms 4244 KB Output is correct
20 Correct 5 ms 4216 KB Output is correct
21 Correct 5 ms 4244 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 5 ms 4216 KB Output is correct
24 Correct 5 ms 4216 KB Output is correct
25 Correct 5 ms 4216 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 30 ms 5892 KB Output is correct
28 Correct 24 ms 5836 KB Output is correct
29 Correct 29 ms 5748 KB Output is correct
30 Correct 26 ms 5876 KB Output is correct
31 Correct 32 ms 5868 KB Output is correct
32 Correct 64 ms 5800 KB Output is correct
33 Correct 29 ms 5876 KB Output is correct
34 Correct 27 ms 5900 KB Output is correct
35 Correct 70 ms 5856 KB Output is correct
36 Correct 65 ms 5972 KB Output is correct
37 Correct 62 ms 5836 KB Output is correct
38 Correct 61 ms 5844 KB Output is correct
39 Correct 64 ms 5960 KB Output is correct
40 Correct 49 ms 5872 KB Output is correct
41 Correct 51 ms 5904 KB Output is correct
42 Correct 46 ms 5896 KB Output is correct
43 Correct 45 ms 5912 KB Output is correct
44 Correct 50 ms 5872 KB Output is correct
45 Correct 49 ms 5868 KB Output is correct
46 Correct 45 ms 5892 KB Output is correct
47 Correct 44 ms 5876 KB Output is correct
48 Correct 805 ms 19172 KB Output is correct
49 Correct 805 ms 19184 KB Output is correct
50 Correct 804 ms 19168 KB Output is correct
51 Correct 689 ms 18984 KB Output is correct
52 Correct 617 ms 17924 KB Output is correct
53 Correct 687 ms 18520 KB Output is correct
54 Correct 652 ms 17376 KB Output is correct
55 Correct 657 ms 17200 KB Output is correct
56 Correct 627 ms 16864 KB Output is correct
57 Execution timed out 2605 ms 168776 KB Time limit exceeded
58 Halted 0 ms 0 KB -