Submission #650117

#	Time	Username	Problem	Language	Result	Execution time	Memory
650117		rsjw	Sails (IOI07_sails)	C++17	100 / 100	47 ms	3732 KiB

sails

#include <bits/stdc++.h>
using namespace std;
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
const int N = 100020;
struct sail {
	int h,a;
	bool operator < (const sail & ri) const {
		return h<ri.h;
	}
}a[N+10];
int t[N+10];
//维护单调不升序列
void update(int x,int I) {
	while(x<=N) {
		t[x]+=I;x+=x&-x;
	}
}
int query(int x) {
	int ans=0; while(x) ans+=t[x],x-=x&-x; return ans;
}
int lower(int x) { //第一个小于等于x 
	int i,sum=0,l=0;
	for(i=17;i>=0;i--) if(l+(1<<i)<=N&&sum+t[l+(1<<i)]>x) l+=(1<<i),sum+=t[l];
	return l+1;
}
signed main() {
	int i,n,j;
	fin>>n;
	for(i=1;i<=n;i++) fin>>a[i].h>>a[i].a;
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++) {
		int L=a[i].h-a[i].a+1,R=a[i].h;
		int t=query(L);
		int l=lower(t);
		int r=lower(t-1);
		
		if(R<r) {
			update(l,1);
			update(l+R-L+1,-1);
		} else {
			update(r,1);
			update(R+1,-1);
			update(l+r-L,-1);
			update(l,1);
		}
	}
	long long ans=0;
	for(i=1;i<=N;i++) {
		int t=query(i);
		ans+=1ll*t*(t-1)/2;
	} fout<<ans;
	return 0;
}

Compilation message (stderr)

sails.cpp: In member function 'IO& IO::operator<<(T)':
sails.cpp:21:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   21 |         while(st[0]) pc('0'+st[st[0]--]);return *this;
      |         ^~~~~
sails.cpp:21:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   21 |         while(st[0]) pc('0'+st[st[0]--]);return *this;
      |                                          ^~~~~~
sails.cpp: In function 'int main()':
sails.cpp:47:10: warning: unused variable 'j' [-Wunused-variable]
   47 |  int i,n,j;
      |          ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10