結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー |
![]() |
提出日時 | 2015-07-23 22:40:14 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,049 bytes |
コンパイル時間 | 846 ms |
コンパイル使用メモリ | 90,748 KB |
実行使用メモリ | 11,164 KB |
最終ジャッジ日時 | 2024-07-08 12:36:48 |
合計ジャッジ時間 | 10,827 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 TLE * 1 -- * 4 |
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> //#include <array> #include <list> #include <queue> #include <vector> #include <complex> #include <set> #include <map> ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)<<endl; #define PII pair<int,int> ///////// typedef long long LL; typedef long double LD; ///////// using namespace::std; ///////// int A[100000],B[100000]; int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;// //cout << setprecision(16);// vector<PII> Avar,Bvar; int L,M,N; cin>>L>>M>>N; int f=-1,b=-1; rep(i,L){ cin>>A[i]; } rep(i,M){ cin>>B[i]; } sort(A,A+L); sort(B,B+M); rep(i,L){ if(b+1==A[i]){ b = A[i]; }else{ if(f!=-1){ Avar.push_back( PII(f,b) ); } f = A[i]; b = A[i]; } } Avar.push_back( PII(f,b) ); f=-1; b=-1; rep(i,M){ if(b+1==B[i]){ b = B[i]; }else{ if(f!=-1){ Bvar.push_back( PII(f,b) ); } f = B[i]; b = B[i]; } } Bvar.push_back( PII(f,b) ); /////////// vector<PII>::iterator Aitr,Bitr; int Q,ans=0; cin>>Q; rep(i,Q){ ans=0; Aitr = Avar.begin(); Bitr = Bvar.begin(); while( Aitr != Avar.end() && Bitr != Bvar.end() ){ if( Aitr->second < (Bitr->first + i) ){ ++Aitr; }else if( (Bitr->second + i) < Aitr->first){ ++Bitr; } else/* if( (Bitr->first + i) <= Aitr->second && Aitr->first <= (Bitr->second + i) )*/{ if(Aitr->first <= (Bitr->first + i) ){ if(Aitr->second <= (Bitr->second + i) ){ ans += Aitr->second - (Bitr->first + i) + 1; ++Aitr; }else{ ans += (Bitr->second + i) - (Bitr->first + i) + 1; ++Bitr; } }else{ if( (Bitr->second + i) <= Aitr->second){ ans += (Bitr->second + i) - Aitr->first + 1; ++Bitr; }else{ ans += Aitr->second - Aitr->first + 1; ++Aitr; } } } } cout << ans << '\n'; } return 0; }