# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
904701 |
2024-01-12T07:37:49 Z |
JakobZorz |
Sails (IOI07_sails) |
C++17 |
|
21 ms |
3164 KB |
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
const int TREE_SIZE=10;
ll tree[TREE_SIZE];
int beg=TREE_SIZE;
ll get_sum(int l,int r){
ll res=0;
for(int i=l;i<r;i++)
res+=tree[i];
return res;
}
int get_first(int v){
int i=beg;
while(i<TREE_SIZE&&tree[i]<v)
i++;
return i;
}
int get_last(int v){ // get one after last
int i=beg;
while(i<TREE_SIZE&&tree[i]<=v)
i++;
return i;
}
void update(int l,int r,int v){
for(int i=l;i<r;i++)
tree[i]+=v;
}
void add(){
beg--;
}
ll get(int k){
if(k==0)
return 0;
int mv=(int)get_sum(beg+k-1,beg+k);
int i1=get_first(mv);
ll res=get_sum(beg,i1);
update(beg,i1,1);
k-=i1-beg;
int i2=get_last(mv);
res+=get_sum(i2-k,i2);
update(i2-k,i2,1);
return res;
}
void solve(){
int n;
cin>>n;
vector<pair<int,int>>arr(n);
for(auto&i:arr)
cin>>i.first>>i.second;
sort(arr.begin(),arr.end());
int ph=0;
multiset<int>s;
ll r=0;
for(auto [h,k]:arr){
for(int i=ph;i<h;i++)
add();
r+=get(k);
ph=h;
}
cout<<r<<"\n";
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
/*
6
3 2
5 3
4 1
2 1
4 3
3 2
10
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
7 ms |
1372 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
11 ms |
1884 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
17 ms |
2444 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
19 ms |
2908 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
21 ms |
3164 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |