Submission #934930

#TimeUsernameProblemLanguageResultExecution timeMemory
934930oblantisExamination (JOI19_examination)C++17
100 / 100
295 ms20964 KiB
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define pb push_back #define ss second #define ff first #define vt vector using namespace std; #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; const int inf = 1e9; const int mod = 1e9+7; const int maxn = 1e6 + 1; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int n, q; tuple<int, int, int, int> t[maxn]; int out[100000]; void ope(int l, int r){ if(l + 1 == r)return; int mid = l + (r - l) / 2; ope(l, mid), ope(mid, r); vt<tuple<int, int, int, int>> ch; ordered_set os; int j = mid - 1, o = r - 1; while(j >= l && o >= mid){ if(get<3>(t[j]) == inf)j--; else if(get<3>(t[o]) != inf)o--; else { if(get<1>(t[j]) <= get<1>(t[o])){ os.insert(get<2>(t[o])); o--; } else { int x = os.size() - os.order_of_key(get<2>(t[j])); out[get<3>(t[j]) - 1] += x; j--; } } } while(j >= l){ if(get<3>(t[j]) != inf){ int x = os.size() - os.order_of_key(get<2>(t[j])); out[get<3>(t[j]) - 1] += x; } j--; } j = l, o = mid; while(j < mid || o < r){ if(o == r || (j < mid && get<1>(t[j]) <= get<1>(t[o])))ch.pb(t[j++]); else ch.pb(t[o++]); } for(int i = l; i < r; i++){ t[i] = ch[i - l]; } } void solve() { cin >> n >> q; for(int i = 0, a, b; i < n; i++){ cin >> a >> b; t[i] = make_tuple(a, b, a + b, inf); } for(int i = 0, a, b, c; i < q; i++){ cin >> a >> b >> c; t[i + n] = make_tuple(a, b, c, i + 1); } sort(t, t + n + q); ope(0, n + q); for(int i = 0; i < q; i++)cout << out[i] << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int times = 1; //cin >> times; for(int i = 1; i <= times; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...