Submission #1050904

#TimeUsernameProblemLanguageResultExecution timeMemory
1050904Dennis_JasonSails (IOI07_sails)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define NMAX 250001 #define int long long #define MAX 100000 #define pb push_back #define eb emplace_back #define MOD 1000000007 #define nl '\n'#include <bits/stdc++.h> #define NMAX 250001 #define int long long #define MAX 100000 #define pb push_back #define eb emplace_back #define MOD 1000000007 #define nl '\n' #define INF 1000000007 #define LLONG_MAX 9223372036854775807 #define pii pair<int,int> #define tpl tuple<int,int,int,int> #pragma GCC optimize("O3") using namespace std; ifstream fin("aib.in"); ofstream fout("aib.out"); vector<int>delta; class segtree{ private: int n; vector<int>before; vector<int>after; public: void init(int sz) { n=sz+1; before.resize(4*sz+1,-1); after.resize(4*sz+1,-1); update(0,MAX); } void update(int node,int st,int dr,int pos,int val) { if(st==dr) { delta[st]+=val; if(delta[st]) before[node]=after[node]=pos; else before[node]=after[node]=-1; return; } int mid=(st+dr)/2; if(pos<=mid) update(2*node,st,mid,pos,val); else update(2*node+1,mid+1,dr,pos,val); before[node]=(before[2*node+1]!=-1? before[2*node+1]:before[2*node]); after[node]=(after[2*node]!=-1? after[2*node]:after[2*node+1]); } int first_after(int node,int st,int dr,int L,int R) { if(st>=R || dr<=L) return -1; if(L<=st && dr<=R) { return after[node]; } int mid=(st+dr)/2; int left=first_after(2*node,st,mid,L,R); int right=first_after(2*node+1,mid+1,dr,L,R); int ans=(left!=-1? left:right); return ans; } int last_before(int node,int st,int dr,int L,int R) { if(st>=R || dr<=L) return -1; if(L<=st && dr<=R) { return before[node]; } int mid=(st+dr)/2; int left=last_before(2*node,st,mid,L,R); int right=last_before(2*node+1,mid+1,dr,L,R); int ans=(right!=-1? right:left); return ans; } void update(int pos,int val) { update(1,0,MAX,pos,val); } int first(int L,int R) { return first_after(1,0,MAX,L,R); } int last(int L,int R) { return last_before(1,0,MAX,L,R); } }; int n,max_h; vector<pii>v; segtree st; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; v.resize(n); for(int i=0;i<n;++i) { cin>>v[i].first>>v[i].second; max_h=max(max_h,v[i].first); } delta.resize(MAX); st.init(MAX); auto cmp=[&](pii a,pii b) { // if(a.first==b.first) // return a.second<b.second; return a.first<b.first; }; sort(v.begin(),v.end(),cmp); for(int i=0;i<n;++i) { int h0=v[i].first-v[i].second; int up=st.first(h0,MAX+1); int down=st.last(0,h0+1); if(up==-1) up=v[i].first; /*------------------DEBUG-------------------- cout<<v[i].first<<" "<<v[i].second<<": "<<nl; cout<<"h0 0-h0+1 h0-maxh+1"<<nl; cout<<h0<<" --- "<<down<<" --- "<<up<<nl<<nl; ------------------------------------------*/ st.update(v[i].first,1); st.update(up,-1); st.update(down+up-h0,1); st.update(down,-1); // for(int i=1;i<=max_h;++i) // { // cout<<delta[i]<<" "; // } // cout<<nl; } int ans=0,aux=0; for(int i=max_h;i>0;--i) { // cout<<delta[i]<<" "; aux+=delta[i]; ans+=(aux*(aux-1))/2; } cout<<ans; return 0; } #define INF 1000000007 #define LLONG_MAX 9223372036854775807 #define pii pair<int,int> #define tpl tuple<int,int,int,int> #pragma GCC optimize("O3") using namespace std; ifstream fin("aib.in"); ofstream fout("aib.out"); vector<int>delta; class segtree{ private: int n; vector<int>before; vector<int>after; public: void init(int sz) { n=sz+1; before.resize(4*sz+1,-1); after.resize(4*sz+1,-1); update(0,n); } void update(int node,int st,int dr,int pos,int val) { if(st==dr) { delta[st]+=val; if(delta[st]) before[node]=after[node]=pos; else before[node]=after[node]=-1; return; } int mid=(st+dr)/2; if(pos<=mid) update(2*node,st,mid,pos,val); else update(2*node+1,mid+1,dr,pos,val); before[node]=(before[2*node+1]!=-1? before[2*node+1]:before[2*node]); after[node]=(after[2*node]!=-1? after[2*node]:after[2*node+1]); } int first_after(int node,int st,int dr,int L,int R) { if(st>=R || dr<=L) return -1; if(L<=st && dr<=R) { return after[node]; } int mid=(st+dr)/2; int left=first_after(2*node,st,mid,L,R); int right=first_after(2*node+1,mid+1,dr,L,R); int ans=(left!=-1? left:right); return ans; } int last_before(int node,int st,int dr,int L,int R) { if(st>=R || dr<=L) return -1; if(L<=st && dr<=R) { return before[node]; } int mid=(st+dr)/2; int left=last_before(2*node,st,mid,L,R); int right=last_before(2*node+1,mid+1,dr,L,R); int ans=(right!=-1? right:left); return ans; } void update(int pos,int val) { update(1,0,n,pos,val); } int first(int L,int R) { return first_after(1,0,n,L,R); } int last(int L,int R) { return last_before(1,0,n,L,R); } }; int n,max_h; vector<pii>v; segtree st; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; v.resize(n); for(int i=0;i<n;++i) { cin>>v[i].first>>v[i].second; max_h=max(max_h,v[i].first); } delta.resize(max_h+1); st.init(max_h); auto cmp=[&](pii a,pii b) { // if(a.first==b.first) // return a.second<b.second; return a.first<b.first; }; sort(v.begin(),v.end(),cmp); for(int i=0;i<n;++i) { int h0=v[i].first-v[i].second; int up=st.first(h0,max_h+1); int down=st.last(0,h0+1); if(up==-1) up=v[i].first; /*------------------DEBUG-------------------- cout<<v[i].first<<" "<<v[i].second<<": "<<nl; cout<<"h0 0-h0+1 h0-maxh+1"<<nl; cout<<h0<<" --- "<<down<<" --- "<<up<<nl<<nl; ------------------------------------------*/ st.update(v[i].first,1); st.update(up,-1); st.update(down+up-h0,1); st.update(down,-1); // for(int i=1;i<=max_h;++i) // { // cout<<delta[i]<<" "; // } // cout<<nl; } int ans=0,aux=0; for(int i=max_h;i>0;--i) { // cout<<delta[i]<<" "; aux+=delta[i]; ans+=(aux*(aux-1))/2; } cout<<ans; return 0; }

Compilation message (stderr)

sails.cpp:15: warning: "nl" redefined
   15 | #define nl '\n'
      | 
sails.cpp:8: note: this is the location of the previous definition
    8 | #define nl '\n'#include <bits/stdc++.h>
      | 
sails.cpp:17: warning: "LLONG_MAX" redefined
   17 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from sails.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      | 
sails.cpp:170:10: error: redefinition of 'std::ifstream fin'
  170 | ifstream fin("aib.in");
      |          ^~~
sails.cpp:22:10: note: 'std::ifstream fin' previously declared here
   22 | ifstream fin("aib.in");
      |          ^~~
sails.cpp:171:10: error: redefinition of 'std::ofstream fout'
  171 | ofstream fout("aib.out");
      |          ^~~~
sails.cpp:23:10: note: 'std::ofstream fout' previously declared here
   23 | ofstream fout("aib.out");
      |          ^~~~
sails.cpp:172:12: error: redefinition of 'std::vector<long long int> delta'
  172 | vector<int>delta;
      |            ^~~~~
sails.cpp:24:12: note: 'std::vector<long long int> delta' previously declared here
   24 | vector<int>delta;
      |            ^~~~~
sails.cpp:173:7: error: redefinition of 'class segtree'
  173 | class segtree{
      |       ^~~~~~~
sails.cpp:25:7: note: previous definition of 'class segtree'
   25 | class segtree{
      |       ^~~~~~~
sails.cpp:249:5: error: redefinition of 'long long int n'
  249 | int n,max_h;
      |     ^
sails.cpp:101:5: note: 'long long int n' previously declared here
  101 | int n,max_h;
      |     ^
sails.cpp:249:7: error: redefinition of 'long long int max_h'
  249 | int n,max_h;
      |       ^~~~~
sails.cpp:101:7: note: 'long long int max_h' previously declared here
  101 | int n,max_h;
      |       ^~~~~
sails.cpp:250:12: error: redefinition of 'std::vector<std::pair<long long int, long long int> > v'
  250 | vector<pii>v;
      |            ^
sails.cpp:102:12: note: 'std::vector<std::pair<long long int, long long int> > v' previously declared here
  102 | vector<pii>v;
      |            ^
sails.cpp:251:9: error: redefinition of 'segtree st'
  251 | segtree st;
      |         ^~
sails.cpp:103:9: note: 'segtree st' previously declared here
  103 | segtree st;
      |         ^~
sails.cpp:252:8: error: redefinition of 'int main()'
  252 | signed main()
      |        ^~~~
sails.cpp:104:8: note: 'int main()' previously defined here
  104 | signed main()
      |        ^~~~