Submission #1079905

#TimeUsernameProblemLanguageResultExecution timeMemory
1079905vjudge1Examination (JOI19_examination)C++17
100 / 100
340 ms49316 KiB
#include<bits/stdc++.h> #define all(x) (x).begin() , (x).end() #define pll pair<long long, long long> #define pii pair<int , int> #define fi first #define se second #define bit(i,j) ((j >> i) & 1) using namespace std; #define int long long const long long inf = 1e18+1; const int mod = 1e9+7; const int MAXN = 3e6+100; struct BIT { int b[MAXN], n; void init(int _n) { n = _n; for(int i = 0 ; i <= n ; ++i) b[i] = 0; } inline int lowbit(int x) { return x & (-x); } void update(int x, int v) { for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v; } int query(int x) { int ans = 0; for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i]; return ans; } } bit; struct Pt{ int x , y , z , i , t; }; Pt a[MAXN]; int ans[MAXN]; void cdq(int l , int r){ if(l == r) return ; int mid = l + r >> 1; cdq(l , mid) ; cdq(mid+1 , r); int i = l, j = mid+1 ,sum = 0; vector<int> record; vector<Pt> tmp; while(i <= mid && j <= r){ if(a[i].y > a[j].y) { if(a[i].t == 0) bit.update(a[i].z , 1) , sum ++ , record.push_back(a[i].z); tmp.push_back(a[i++]); } else{ ans[a[j].i] += sum - bit.query(a[j].z); tmp.push_back(a[j++]); } } while(i <= mid) tmp.push_back(a[i++]); while(j <= r) ans[a[j].i] += sum - bit.query(a[j].z), tmp.push_back(a[j++]); for(int i = l ; i <= r ; i++) a[i] = tmp[i-l]; for(auto i : record) bit.update(i , -1); vector<int> ().swap(record); vector<Pt> ().swap(tmp); } map<int , int> mp; int32_t main(){ //freopen("KNIGHTGAME.inp", "r", stdin); //freopen("KNIGHTGAME.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int n , q; cin >> n >> q; vector<int> comp; for(int i = 1 ; i <= n ; i++) cin >> a[i].x >> a[i].y, a[i].i = i , a[i].z = a[i].x + a[i].y, a[i].t = 0 , comp.push_back(a[i].z); for(int j = 1 ; j <= q ; j ++){ int x , y , z; cin>> x >> y >> z; a[n + j] = {x-1 , y-1 , z-1 , n + j , 1}; comp.push_back(z-1); } sort(all(comp)); comp.erase(unique(comp.begin() , comp.end()) , comp.end()); for(int i = 0 ; i < comp.size() ;i++) mp[comp[i]] = i+1; for(int i = 1 ; i <= n + q ; i++) a[i].z = mp[a[i].z]; sort(a+1, a+n+q+1, [&](auto a, auto b) { return (a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x > b.x); }); bit.init(n + q); cdq(1 , n + q); for(int i = 1 ; i <= q ; i++) cout << ans[i + n] << "\n"; return 0; }

Compilation message (stderr)

examination.cpp: In function 'void cdq(long long int, long long int)':
examination.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid = l + r >> 1;
      |            ~~^~~
examination.cpp: In function 'int32_t main()':
examination.cpp:77:20: 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]
   77 |  for(int i = 0 ; i < comp.size() ;i++) mp[comp[i]] = i+1;
      |                  ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...