fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ii pair<int,int>
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. const int N=2e6+10;
  8. struct p{
  9.     int l, r,id;
  10.     p(int x,int y,int z){
  11.         l=x;
  12.         r=y;
  13.         id=z;
  14.     }
  15. };
  16. bool cmp(p x,p y){
  17.     return x.l<=y.l;
  18. }
  19. vector<p> v[N];
  20. int a[N],b[N],c[N],m[N],ans[N];
  21. void solve(){
  22.     int n;
  23.     cin>>n;
  24.     int res=0;
  25.     for(int i=1;i<=n;i++){
  26.         cin>>a[i]>>b[i]>>m[i];
  27.         v[a[i]+b[i]-m[i]].pb(p(a[i]-m[i],a[i],i));
  28.     }
  29.     for(int i=1;i<=n;i++){
  30.         int k=a[i]+b[i]-m[i];
  31.         vector<int> tem;
  32.         tem.clear();
  33.         sort(v[k].begin(),v[k].end(),cmp);
  34.         int dau,cuoi=-1;
  35.         for(int j=0;j<v[k].size();j++){
  36.             int t=max(0,v[k][j].l);
  37.             if(cuoi<t){
  38.                 res++;
  39.                 for(auto x:tem) ans[x]=a[x]-dau;
  40.                 dau=t;
  41.                 cuoi=v[k][j].r;
  42.                 tem.clear();
  43.                 tem.pb(v[k][j].id);
  44.             }
  45.             else{
  46.                 dau=max(dau,t);
  47.                 cuoi=min(cuoi,v[k][j].r);
  48.                 tem.pb(v[k][j].id);
  49.             }
  50.         }
  51.         for(auto x:tem) ans[x]=a[x]-dau;
  52.         v[k].clear();
  53.     }
  54.     cout<<res<<'\n';
  55.     for(int i=1;i<=n;i++){
  56.         cout<<ans[i]<<' '<<m[i]-ans[i]<<'\n';
  57.     }    
  58.  
  59. }
  60. int32_t main(){
  61.     ios_base::sync_with_stdio(0);
  62.     cin.tie(0);cout.tie(0);
  63.     int tt;
  64.     cin>>tt;
  65.     while(tt--){
  66.         solve();
  67.     }
  68. }
Success #stdin #stdout 0.02s 57596KB
comments (?)
stdin
copy 
5

3
10 10 2
9 9 0
10 9 1

2
3 4 1
5 1 2

3
7 2 5
6 5 4
5 5 6

1
13 42 50

5
5 7 12
3 1 4
7 3 7
0 0 0
4 1 5
stdout
copy 
1
1 1
0 0
1 0
2
1 0
2 0
2
5 0
4 0
3 3
1
13 37
2
5 7
3 1
7 0
0 0
4 1
https://ideone.com/64cEbJ
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!