oj.uz

Submission #120529

# Submission time Handle Problem Language Result Execution time Memory
120529 2019-06-24T18:09:11 Z gs14004 Strange Device (APIO19_strange_device) C++17
50 / 100
 5000 ms 357436 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXT = 4200000;
using lint = long long;
using pi = pair<lint, lint>;

lint gcd(lint x, lint y){
	return y ? gcd(y, x%y) : x;
}

struct event{
	lint pos, st, ed;
	int dx;
	bool operator<(const event &e)const{
		return pos != e.pos ? pos < e.pos : dx > e.dx;
	}
};

struct strip{
	lint fuck, pos, dx;
	bool operator<(const strip &s)const{
		return pi(fuck, pos) < pi(s.fuck, s.pos);
	}
};

int n;
lint a, b, l[MAXN], r[MAXN];
map<lint, int> mp;
vector<strip> strips;

int main(){
	scanf("%d",&n);
	scanf("%lld %lld",&a,&b);
	for(int i=0; i<n; i++){
		scanf("%lld %lld",&l[i],&r[i]);
	}
	lint period = a / gcd(a, b + 1);
	for(int i=0; i<n; i++){
		vector<lint> v = {l[i] % b, 0, (r[i] + 1) % b};
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end()) - v.begin());
		int ptr = 0;
		vector<event> tev;
		map<lint, int> dx;
		int cnt = 0;
		for(auto &j : v){
			ptr++;
			lint s = l[i] + b - j;
			lint e = r[i] + b - j;
			s = (s + b - 1) / b;
			e /= b;
			lint is = j;
			lint ie = (ptr < v.size() ? v[ptr] : b);
			if(e - s + 1 >= period){
				tev.push_back({is, 0, period, +1});
				tev.push_back({ie, 0, period, -1});
				dx[0]++;
				dx[period]--;
			}
			else if(s <= e){
				if(s % period > e % period){
					tev.push_back({is, s % period, period, +1});
					tev.push_back({ie, s % period, period, -1});
					tev.push_back({is, 0, e % period + 1, +1});
					tev.push_back({ie, 0, e % period + 1, -1});
					dx[s % period]++;
					dx[period]--;
					dx[0]++;
					dx[e % period + 1]--;
				}
				else{
					tev.push_back({is, s % period, e % period + 1, +1});
					tev.push_back({ie, s % period, e % period + 1, -1});
					dx[s % period]++;
					dx[e % period + 1]--;
				}
			}
			cnt++;
		}
		auto nitr = dx.begin();
		int tcnt = 0;
		for(auto &i : dx){
			nitr++;
			tcnt += i.second;
			if(nitr == dx.end()) break;
			if(tcnt == cnt){
				mp[i.first]++;
				mp[nitr->first]--;
			}
			else{
				for(auto &j : tev){
					lint st = max(i.first, j.st);
					lint ed = min(nitr->first, j.ed);
					for(lint jj = st; jj < ed; jj++){
						strips.push_back({jj, j.pos, j.dx});
					}
				}
			}
		}
	}
	auto nitr = mp.begin();
	int tcnt = 0;
	vector<lint> v;
	lint ret = 0;
	for(auto &i : mp){
		nitr++;
		tcnt += i.second;
		if(tcnt > 0 && nitr != mp.end()){
			ret += b * (nitr->first - i.first);
		}
		if(tcnt > 0){
			v.push_back(i.first);
			v.push_back(nitr->first);
		}
	}
	sort(strips.begin(), strips.end());
	for(int i=0; i<strips.size(); ){
		int e = i;
		while(e < strips.size() && strips[e].fuck == strips[i].fuck) e++;
		auto l = lower_bound(v.begin(), v.end(), strips[i].fuck + 1) - v.begin();
		if(l % 2 == 1){
			i = e;
			continue;
		}
		int cnt = 0;
		for(int j = i; j + 1 < e; j++){
			cnt += strips[j].dx;
			if(cnt > 0) ret += strips[j + 1].pos - strips[j].pos;
		}
		i = e;
	}
	cout << ret << endl;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    lint ie = (ptr < v.size() ? v[ptr] : b);
               ~~~~^~~~~~~~~~
strange_device.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<strips.size(); ){
               ~^~~~~~~~~~~~~~
strange_device.cpp:120:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e < strips.size() && strips[e].fuck == strips[i].fuck) e++;
         ~~^~~~~~~~~~~~~~~
strange_device.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
strange_device.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~
strange_device.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 14 ms 1396 KB Output is correct
3 Correct 14 ms 1396 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 312 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 14 ms 1396 KB Output is correct
17 Correct 135 ms 8228 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 762 ms 16008 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1419 ms 95140 KB Output is correct
3 Correct 1488 ms 95144 KB Output is correct
4 Correct 1556 ms 95196 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1419 ms 95140 KB Output is correct
3 Correct 1488 ms 95144 KB Output is correct
4 Correct 1556 ms 95196 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2766 ms 267312 KB Output is correct
7 Correct 1248 ms 65468 KB Output is correct
8 Correct 2796 ms 267320 KB Output is correct
9 Correct 3279 ms 267312 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1419 ms 95140 KB Output is correct
3 Correct 1488 ms 95144 KB Output is correct
4 Correct 1556 ms 95196 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 175 ms 14396 KB Output is correct
7 Correct 346 ms 37628 KB Output is correct
8 Correct 350 ms 37644 KB Output is correct
9 Correct 348 ms 37608 KB Output is correct
10 Correct 174 ms 14408 KB Output is correct
11 Correct 288 ms 29996 KB Output is correct
12 Correct 314 ms 40392 KB Output is correct
13 Correct 304 ms 27396 KB Output is correct
14 Correct 137 ms 8284 KB Output is correct
15 Correct 364 ms 26992 KB Output is correct
16 Correct 132 ms 8192 KB Output is correct
17 Correct 350 ms 38188 KB Output is correct
18 Correct 3667 ms 334168 KB Output is correct
19 Correct 3727 ms 334344 KB Output is correct
20 Execution timed out 5035 ms 357436 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 130 ms 8180 KB Output is correct
3 Correct 132 ms 8184 KB Output is correct
4 Correct 1942 ms 114596 KB Output is correct
5 Correct 138 ms 8160 KB Output is correct
6 Correct 137 ms 8160 KB Output is correct
7 Correct 143 ms 8148 KB Output is correct
8 Correct 152 ms 8136 KB Output is correct
9 Correct 141 ms 8240 KB Output is correct
10 Correct 135 ms 8188 KB Output is correct
11 Correct 130 ms 8144 KB Output is correct
12 Correct 120 ms 8240 KB Output is correct
13 Correct 149 ms 8264 KB Output is correct
14 Correct 1396 ms 65396 KB Output is correct
15 Correct 139 ms 8328 KB Output is correct
16 Correct 1218 ms 65416 KB Output is correct
17 Correct 1625 ms 114572 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 14 ms 1396 KB Output is correct
3 Correct 14 ms 1396 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 312 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 14 ms 1396 KB Output is correct
17 Correct 135 ms 8228 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 296 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 252 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 5 ms 632 KB Output is correct
26 Correct 4 ms 504 KB Output is correct
27 Correct 4 ms 504 KB Output is correct
28 Correct 762 ms 16008 KB Output is correct
29 Correct 2 ms 348 KB Output is correct
30 Correct 1419 ms 95140 KB Output is correct
31 Correct 1488 ms 95144 KB Output is correct
32 Correct 1556 ms 95196 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2766 ms 267312 KB Output is correct
35 Correct 1248 ms 65468 KB Output is correct
36 Correct 2796 ms 267320 KB Output is correct
37 Correct 3279 ms 267312 KB Output is correct
38 Correct 2 ms 376 KB Output is correct
39 Correct 175 ms 14396 KB Output is correct
40 Correct 346 ms 37628 KB Output is correct
41 Correct 350 ms 37644 KB Output is correct
42 Correct 348 ms 37608 KB Output is correct
43 Correct 174 ms 14408 KB Output is correct
44 Correct 288 ms 29996 KB Output is correct
45 Correct 314 ms 40392 KB Output is correct
46 Correct 304 ms 27396 KB Output is correct
47 Correct 137 ms 8284 KB Output is correct
48 Correct 364 ms 26992 KB Output is correct
49 Correct 132 ms 8192 KB Output is correct
50 Correct 350 ms 38188 KB Output is correct
51 Correct 3667 ms 334168 KB Output is correct
52 Correct 3727 ms 334344 KB Output is correct
53 Execution timed out 5035 ms 357436 KB Time limit exceeded
54 Halted 0 ms 0 KB -