Submission #140842

#TimeUsernameProblemLanguageResultExecution timeMemory
140842karmaExamination (JOI19_examination)C++11
43 / 100
2964 ms1048576 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define FileName "test" #define ll long long #define ld long double #define ull unsigned long long #define Debug(x) cerr << #x << "is " << x << '\n'; #define pb emplace_back #define mp make_pair #define x first #define y second //#define LuckyAurora //#pragma GCC target ("avx2") #pragma GCC optimization ("O3") //#pragma GCC optimization ("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") using namespace std; using namespace __gnu_pbds; template<typename T> inline void Cin(T &x) { char c; T sign = 1; x = 0; for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') sign = -1; for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0'; x *= sign; } template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');} template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);} template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);} template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);} typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; typedef pair<int, int> pii; const int N = int(1e5) + 7; struct TSegment { bool Get(int x, int i) {return (x >> i) & 1;} struct TTrie {TTrie* chil[2]; int cur;} *t[N << 2]; typedef TTrie* PTrie; PTrie Node() { PTrie ptr = new TTrie(); ptr -> chil[0] = ptr -> chil[1] = NULL, ptr -> cur = 0; return ptr; } void Update(int x, PTrie ptr) { bool bit; ++ptr -> cur; for(int i = 31; i >= 0; --i) { bit = Get(x, i); if(ptr -> chil[bit] == NULL) ptr -> chil[bit] = Node(); ptr = ptr -> chil[bit]; ++ptr -> cur; } } int Count(int x, PTrie ptr) { int res = ptr -> cur; bool bit; for(int i = 31; i >= 0; --i) { bit = Get(x, i); if(bit && ptr -> chil[0]) res -= ptr -> chil[0] -> cur; if(ptr -> chil[bit] == NULL) return res; ptr = ptr -> chil[bit]; } return res; } int l[N << 2], h[N << 2]; void Build(int x, int low, int high) { l[x] = low, h[x] = high; t[x] = Node(); if(l[x] == h[x]) {return;} int mid = (low + high) >> 1; Build(x << 1, low, mid); Build(x << 1 | 1, mid + 1, high); } void Update(int x, int pos, int val) { if(l[x] > pos || h[x] < pos) return; if(l[x] <= pos && pos <= h[x]) Update(val, t[x]); if(l[x] == h[x]) return; Update(x << 1, pos, val); Update(x << 1 | 1, pos, val); } int Query(int x, int low, int high, int val) { if(l[x] > high || h[x] < low) return 0; if(l[x] >= low && h[x] <= high) return Count(val, t[x]); return Query(x << 1, low, high, val) + Query(x << 1 | 1, low, high, val); } } irene; int n, Q, res[N]; pii a[N]; vector<int> v; struct TQuery { int a, b, c, id; bool operator <(const TQuery& other)const& { return a > other.a; } } q[N]; void Enter() { cin >> n >> Q; for(int i = 1; i <= n; ++i) { cin >> a[i].x >> a[i].y; v.pb(a[i].y); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); sort(a + 1, a + n + 1, [](const pii& a, const pii& b){ return a.x > b.x; }); } void Solve() { for(int i = 1; i <= Q; ++i) { cin >> q[i].a >> q[i].b >> q[i].c; q[i].id = i; } sort(q + 1, q + Q + 1); int j = 1, p; irene.Build(1, 1, int(v.size())); for(int i = 1; i <= Q; ++i) { while(a[j].x >= q[i].a && j <= n) { p = lower_bound(v.begin(), v.end(), a[j].y) - v.begin() + 1; irene.Update(1, p, a[j].x + a[j].y); ++j; } p = lower_bound(v.begin(), v.end(), q[i].b) - v.begin() + 1; res[q[i].id] = irene.Query(1, p, int(v.size()), q[i].c); } for(int i = 1; i <= Q; ++i) cout << res[i] << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(FileName".inp", "r")) { freopen(FileName".inp", "r", stdin); freopen(FileName".out", "w", stdout); } /*int nTest; cin >> nTest; while(nTest --)*/ Enter(), Solve(); return 0; }

Compilation message (stderr)

examination.cpp:15:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
examination.cpp: In function 'int main()':
examination.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...