Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Miles Morales : When will I know I'm ready?
- Peter B. Parker : You won't. It's a leap of faith. That's all it is, Miles. A leap of faith.
- */
- //KEEP IT SIMPLE STUPID
- #include <bits/stdc++.h>
- using namespace std;
- /*================PRAGMAS START===============================================*/
- #pragma GCC optimize("O3")
- #pragma GCC target("avx")
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- /*================PRAGMAS END===============================================*/
- /*=================DEFINES/TYPEDEF START==============================*/
- #define int long long
- #define FIO \
- freopen("input.txt", "r", stdin); \
- freopen("output.txt", "w", stdout);
- #define Lightspeed \
- ios::sync_with_stdio(0); \
- cin.tie(0); \
- cout.tie(0);
- #define google cout << "Case #" << tt << ": "
- #define umin(...) min({__VA_ARGS__})
- #define umax(...) max({__VA_ARGS__})
- #define MAX(v) *max_element(all(v))
- #define MIN(v) *min_element(all(v))
- #define fi first
- #define se second
- /*=================DEFINES/TYPEDEF END================================*/
- /*=================DEBUGGING START====================================*/
- vector<string> split(const string &s, char c)
- {
- vector<string> v;
- stringstream ss(s);
- string x;
- while (getline(ss, x, c))
- v.emplace_back(x);
- return move(v);
- }
- template <typename T, typename... Args>
- inline string arrStr(T arr, int n)
- {
- stringstream s;
- s << "[";
- for (int i = 0; i < n - 1; i++)
- s << arr[i] << ",";
- s << arr[n - 1] << "]";
- return s.str();
- }
- #ifndef ONLINE_JUDGE
- #define debug(args...) \
- { \
- __evars_begin(__LINE__); \
- __evars(split(#args, ',').begin(), args); \
- }
- inline void __evars_begin(int line)
- {
- cerr << "#" << line << ": ";
- }
- template <typename T>
- inline void __evars_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
- template <typename T>
- inline void __evars_out_var(T *val) { cerr << arrStr(val, 10); }
- template <typename T>
- inline void __evars_out_var(T val) { cerr << val; }
- inline void __evars(vector<string>::iterator it) { cerr << endl; }
- template <typename T, typename... Args>
- inline void __evars(vector<string>::iterator it, T a, Args... args)
- {
- cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
- __evars_out_var(a);
- cerr << "; ";
- __evars(++it, args...);
- }
- // #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
- #else
- #define debug(...) 42
- #endif
- /*===============================DEBUGGING END======================*/
- /*=======================CONSTANTS START============================*/
- const int INF = 1e18;
- const int MOD = 1e9 + 7;
- /*=======================CONSTANTS END==============================*/
- /*======================SOME USEFUL FUNCTIONS START=======================*/
- void usaco(string prob)
- {
- freopen((prob + ".in").c_str(), "r", stdin);
- freopen((prob + ".out").c_str(), "w", stdout);
- }
- int gcd(int a, int b)
- {
- return __gcd(a, b);
- }
- int lcm(int a, int b)
- {
- return (a * b) / __gcd(a, b);
- }
- int bpow(int a, int n)
- {
- int res = 1;
- a %= MOD;
- while (n > 0)
- {
- if (n & 1)
- {
- res *= a;
- res %= MOD;
- }
- a *= a;
- a %= MOD;
- n >>= 1;
- }
- return res;
- }
- bool isPrime(int n)
- {
- if (n < 2)
- {
- return false;
- }
- for (int i = 2; i * i <= n; i++)
- {
- if (n % i == 0)
- {
- return false;
- }
- }
- return true;
- }
- /*======================SOME USEFUL FUNCTIONS END=======================*/
- void brute()
- {
- vector<int> prob(1005, 0);
- int n, m;
- cin >> n >> m;
- vector<int> s(m);
- for (int i = 0; i < n; i++)
- {
- int a, b;
- cin >> a >> b;
- for (int j = a; j <= b; j++)
- {
- prob[j]++;
- }
- }
- for (auto &x : s)
- {
- cin >> x;
- }
- vector<int> ans;
- for (int i = 0; i < m; i++)
- {
- int diff = 1e18, p = 0;
- for (int j = 1; j <= 1000; j++)
- {
- if (prob[j] != 0)
- {
- if (abs(j - s[i]) < diff)
- {
- diff = abs(j - s[i]);
- p = j;
- }
- }
- }
- ans.push_back(p);
- prob[p] = 0;
- }
- for (auto x : ans)
- {
- cout << x << " ";
- }
- cout << "\n";
- }
- void solve()
- {
- int n, m;
- cin >> n >> m;
- vector<int> S(m), ans;
- map<int, int> mp;
- for (int i = 0; i < n; i++)
- {
- int a, b;
- cin >> a >> b;
- mp[a] = b;
- }
- for (auto &s : S)
- {
- cin >> s;
- }
- for (int s : S)
- {
- if (mp.upper_bound(s) == mp.begin())
- {
- // if all problems are more difficult than S
- auto p = *mp.begin();
- ans.push_back(p.fi);
- mp.erase(p.fi);
- if (p.fi + 1 <= p.se)
- {
- mp.insert({p.fi + 1, p.se});
- }
- }
- else
- {
- auto kth = mp.upper_bound(s);
- auto previous = prev(kth);
- auto p = *previous;
- /*
- l<=s<=r or r < s
- */
- if (p.fi <= s and s <= p.se)
- {
- // l<= s <=r
- ans.push_back(s);
- if (s - 1 >= p.fi)
- {
- mp[p.fi] = s - 1;
- }
- else
- {
- mp.erase(p.fi);
- }
- if (s + 1 <= p.se)
- {
- mp[s + 1] = p.se;
- }
- else
- {
- if (mp.count(s + 1))
- {
- mp.erase(s + 1);
- }
- }
- }
- else
- {
- // r < s < l(next)
- if (kth != mp.end())
- {
- // if s is the most difficult problem now
- auto next = *kth;
- if (abs(s - p.se) <= abs(s - next.fi))
- {
- ans.push_back(p.se);
- if (p.se - 1 >= p.fi)
- {
- mp[p.fi] = p.se - 1;
- }
- else
- {
- mp.erase(p.fi);
- }
- }
- else
- {
- ans.push_back(next.fi);
- mp.erase(next.fi);
- if (next.fi + 1 <= next.se)
- {
- mp.insert({next.fi + 1, next.se});
- }
- }
- }
- else
- {
- ans.push_back(p.se);
- if (p.se - 1 >= p.fi)
- {
- mp[p.fi] = p.se - 1;
- }
- else
- {
- mp.erase(p.fi);
- }
- }
- }
- }
- }
- for (auto x : ans)
- {
- cout << x << " ";
- }
- cout << "\n";
- }
- signed main()
- {
- // FIO;
- Lightspeed;
- //usaco("cowlands");
- int TC = 1;
- cin >> TC;
- for (int tt = 1; tt <= TC; tt++)
- {
- google;
- solve();
- }
- return 0;
- }
- /* stuff you should look for
- * int overflow, array bounds
- * special cases (n=1?)
- * do smth instead of nothing and stay organized
- * WRITE STUFF DOWN
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement