제출 #103010

#제출 시각아이디문제언어결과실행 시간메모리
103010DystoriaXSails (IOI07_sails)C++14
75 / 100
108 ms2676 KiB
#include <bits/stdc++.h> using namespace std; int bit[100010]; int n; vector<pair<int, int> > v; const int mx = 100001; int getVal(int x){ int ret = 0; for(; x > 0; x -= (x & (-x))) ret += bit[x]; return ret; } void updPos(int x){ for(; x <= mx; x += (x & (-x))) bit[x]++; } void updMin(int x){ for(; x <= mx; x += (x & (-x))) bit[x]--; } int main(){ scanf("%d", &n); v.resize(n); for(int i = 0; i < n; i++) scanf("%d%d", &v[i].first, &v[i].second); sort(v.begin(), v.end()); for(auto it : v){ int h, k; tie(h, k) = it; int l = h - k + 1; // cout << "Proc: " << h << " " << k << endl; // cout << "with val " << l << endl; // cout << getVal(l - 1) << " " << getVal(l) << endl; //cout << "HERE\n" << l << " " << L << " " << R << " " << R - l + L << endl; if(l == 1 || getVal(l - 1) > getVal(l)){ updPos(l); updMin(h + 1); //cout << "Updated: " << l << " " << h << endl; } else { int L = 0, R = h + 1; int lo = 0, hi = h + 1; int tmp = getVal(l); //Find lowerbound while(lo <= hi){ int mid = (lo + hi) >> 1; if(getVal(mid) > tmp){ lo = mid + 1; L = mid; } else hi = mid - 1; } L++; lo = 0, hi = h + 1; //Find upperbound while(lo <= hi){ int mid = (lo + hi) >> 1; if(getVal(mid) >= tmp){ lo = mid + 1; } else R = mid, hi = mid - 1; } //cout << "Same Segments: " << L << " " << R << "\n"; //Update [R + 1, H] and [L, L + remaining length] if(R <= h) updPos(R), updMin(h + 1); updPos(L); updMin(R - l + L); //cout << "Updated: " << L << " " << R - l + L - 1 << endl; } } long long ans = 0; for(int i = 0; i <= 100000; i++){ long long tp = getVal(i); ans += tp * (tp - 1) / 2; } printf("%lld\n", ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sails.cpp: In function 'int main()':
sails.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
sails.cpp:29:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < n; i++) scanf("%d%d", &v[i].first, &v[i].second);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...