Submission #1303789

#TimeUsernameProblemLanguageResultExecution timeMemory
1303789cansu_mutluSails (IOI07_sails)C++20
0 / 100
20 ms2768 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int mxn = 3*1e5+5; /*vector<int> s(mxn*4,0),add(4*mxn,0),a(mxn,0); void ekle(int node,int l,int r,int x,int y) { if(l>=x && r<=y) { add[node]++; } }*/ int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vector<array<int,2>> val(n); for(int i=0;i<n;i++) cin >> val[i][0] >> val[i][1]; sort(val.begin(),val.end()); vector<int> a(val.back()[0]+2,0); int cur = 1; for(int i=0;i<n;i++) { int kac = val[i][1]; int mx = val[i][0]; int son = min(mx,cur+kac-1); int elde = max(0LL,cur+kac-1-mx); a[cur]++; a[son+1]--; cur = son+1; if(cur>mx) { if(elde) { a[1]++; a[elde+1]--; } cur = elde+1; } } for(int i=1;i<a.size();i++) a[i]+= a[i-1]; int sum = 0; for(int i=1;i<a.size();i++) { sum+=a[i]*(a[i]-1)/2; //cout << a[i] << endl; } cout << sum << endl; }
#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...