Submission #1040854

#TimeUsernameProblemLanguageResultExecution timeMemory
1040854minhquaanzFortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
289 ms67904 KiB
/*Code by TMQ*/ #include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define ld long double #define task "1" #define ii pair<ll, ll > #define fi first #define se second #define pb push_back #define em emplace #define all(x) (x).begin(), (x).end() #define sall(x) sort(all(x)) #define rall(x) reverse(all(x)) #define reset(a, x) (memset(a, x, sizeof(a))); #define testcase ll tc; cin >> tc; while(tc--) solve(); ll inline gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); } ll inline lcm(ll a, ll b) { return (a / gcd(a, b) * b); } ///============================================================================ #define BIT(i,mask) ((mask >> (i-1)) & 1) #define DAOBIT(i,mask) ((mask ^ (1<<i-1))) #define OFFBIT(i,mask) ((mask & ~(1 << (i - 1)))) #define ONBIT(i,mask) ((mask | (1 << (i - 1)))) ///============================================================================ const ll mod = 1000000007; const ll mod1 = 998244353; const ll inf = 1000000000000000000 + 10; const ll nmax = 200002; ///============================================================================ using namespace std; ///============================================================================ ll a[nmax], b[nmax], query[nmax]; ll n, k; ll res; vector<ll> t[nmax * 4]; vector<ll> operator +(vector<ll>& a, vector<ll>& b) { vector<ll> ans; ll i, j; i = j = 0; while (i < a.size() && j < b.size()) { if (a[i] < b[j]) ans.pb(a[i++]); else ans.pb(b[j++]); } for (; i < a.size(); ++i) ans.pb(a[i]); for (; j < b.size(); ++j) ans.pb(b[j]); return ans; } void build(ll l, ll r, ll k = 1) { if (l == r) { t[k].pb(query[l]); return; } ll mid = (l + r) >> 1; build(l, mid, k << 1); build(mid + 1, r, k << 1 | 1); t[k] = t[k << 1] + t[k << 1 | 1]; } ii get(ll l, ll r, ll x, ll y, ll k = 1) { auto it = lower_bound(all(t[k]), x); if (it == t[k].end()) return{ 0, 0 }; if (*it >= y) return { 0, t[k].end() - it }; ll mid = (l + r) >> 1; if (l == r) { ///if (*it >= x && *it <= y) return { 1, 0 }; } ii get2 = get(mid + 1, r, x, y, k * 2 + 1); if (get2.fi) return get2; ii get1 = get(l, mid, x, y, k * 2); return { get1.fi + get2.fi, get1.se + get2.se }; } ///============================================================================ int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ///freopen(task".inp", "r", stdin); ///freopen(task".outt", "w", stdout); cin >> n >> k; for (ll i = 1; i <= n; i++) cin >> a[i] >> b[i]; for (ll i = 1; i <= k; i++) cin >> query[i]; build(1, k); // for (auto x : t[1]) // cout << x << ' '; for (ll i = 1; i <= n; i++) { ii ans = get(1, k, min(a[i], b[i]), max(a[i], b[i])); if (ans.fi > 0 && a[i] < b[i]) swap(a[i], b[i]); if (ans.se % 2 == 0) res += a[i]; else res += b[i]; } cout << res; return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'std::vector<long long int> operator+(std::vector<long long int>&, std::vector<long long int>&)':
fortune_telling2.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while (i < a.size() && j < b.size())
      |            ~~^~~~~~~~~~
fortune_telling2.cpp:41:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while (i < a.size() && j < b.size())
      |                            ~~^~~~~~~~~~
fortune_telling2.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (; i < a.size(); ++i)
      |            ~~^~~~~~~~~~
fortune_telling2.cpp:49:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (; j < b.size(); ++j)
      |            ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...