# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
199785 | 2020-02-03T11:01:12 Z | Mercenary | Sails (IOI07_sails) | C++14 | 64 ms | 1888 KB |
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/trie_policy.hpp> #define pb push_back #define mp make_pair #define taskname "A" using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int maxn = 1e5 + 5; int n; ii a[maxn]; int bit[maxn]; int q(int x){ int res = 0; for( ; x > 0 ; x &= x - 1){ res += bit[x]; } return res; } int b(int r , int val){ int pos = 0; for(int i = 16 ; i >= 0 ; --i){ if(pos + (1 << i) <= r && bit[pos + (1 << i)] < val){ val -= bit[pos + (1 << i)];pos += (1 << i); } } return pos+1; } void u(int x , int val){ for( ; x < maxn ; x += x & -x){ bit[x]+=val; } } void u(int l , int r , int val){ u(l,val);u(r+1,-val); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")){ freopen(taskname".INP", "r",stdin); freopen(taskname".OUT", "w",stdout); } cin >> n; for(int i = 0 ; i < n ; ++i)cin >> a[i].first >> a[i].second; sort(a , a + n,greater<ii>()); for(int i = 0 ; i < n ; ++i){ int h , k;tie(h,k) = a[i]; int val = q(k); int ft = b(h,val); int lt = min(h,b(h,val+1)-1); int tmp = (k - ft + 1); u(lt-tmp+1,lt,1); k -= tmp; u(ft-k,ft-1,1); } ll res = 0; for(int i = 1 ; i < maxn ; ++i){ int tmp = q(i); res += (ll)tmp * (tmp - 1) / 2; } cout << res; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 376 KB | Output is correct |
2 | Correct | 6 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 380 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 380 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 248 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 632 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 23 ms | 1148 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 42 ms | 1324 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 57 ms | 1656 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 1784 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 64 ms | 1888 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |