oj.uz

답안 #1044837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1044837 2024-08-05T14:04:02 Z vjudge1 이상한 기계 (APIO19_strange_device) C++17
15 / 100
 1478 ms 524288 KB 
#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff fir -st
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int32_t main(){
	int n,a,b;
	cin>>n>>a>>b;
	if(a>1000000 || b>1000000 || a*b>1000000){
		set<pair<int,int>>st;
		for(int i=0;i<n;i++){
			int l,r;
			cin>>l>>r;
			for(int j=l;j<=r;j++){
				st.insert(make_pair((j+(j/b))%a,j%b));
			}
		}
		cout<<st.size()<<endl;
		return 0;
	}
	set<pair<int,int>>st;
	map<pair<int,int>,int>mp;
	for(int i=0;!st.count(make_pair((i+i/b)%a,i%b));i++){
		st.insert(make_pair((i+i/b)%a,i%b));
		mp[make_pair((i+i/b)%a,i%b)]=i;
	}
	vector<int>pre(st.size()+5);
	for(int i=0;i<n;i++){
		int l,r;
		cin>>l>>r;
		if(r-l+1>=st.size()){
			cout<<st.size()<<endl;
			return 0;
		}
		int x=mp[make_pair((l+l/b)%a,l%b)],y=mp[make_pair((r+r/b)%a,r%b)];
		if(x>y){
			pre[0]++;
			pre[y+1]--;
			pre[x]++;
			pre[st.size()]--;
		}
		else{
			pre[x]++;
			pre[y+1]--;
		}
	}
	int ans=0;
	for(int i=0;i<st.size();i++){
		pre[i]+=(i==0?0:pre[i-1]);
		ans+=(pre[i]!=0);
	}
	cout<<ans<<endl;
}

Compilation message

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:37:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   if(r-l+1>=st.size()){
      |      ~~~~~^~~~~~~~~~~
strange_device.cpp:54:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<st.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 12368 KB Output is correct
3 Correct 41 ms 18004 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 4 ms 2140 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 32 ms 16260 KB Output is correct
16 Correct 80 ms 25268 KB Output is correct
17 Correct 78 ms 6584 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1478 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 468 ms 128552 KB Output is correct
3 Correct 454 ms 129976 KB Output is correct
4 Correct 412 ms 108012 KB Output is correct
5 Correct 975 ms 133204 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 786 ms 62804 KB Output is correct
3 Runtime error 1164 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 786 ms 62804 KB Output is correct
3 Runtime error 1164 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 786 ms 62804 KB Output is correct
3 Runtime error 1164 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Runtime error 965 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 30 ms 12368 KB Output is correct
3 Correct 41 ms 18004 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 4 ms 2140 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 32 ms 16260 KB Output is correct
16 Correct 80 ms 25268 KB Output is correct
17 Correct 78 ms 6584 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Runtime error 1478 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -