oj.uz

Submission #650117

# Submission time Handle Problem Language Result Execution time Memory
650117 2022-10-12T13:14:29 Z rsjw Sails (IOI07_sails) C++17
100 / 100
 47 ms 3732 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 308 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 10 ms 1108 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1236 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1980 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3004 KB Output is correct
2 Correct 27 ms 3072 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3460 KB Output is correct
2 Correct 22 ms 2776 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3732 KB Output is correct
2 Correct 26 ms 3212 KB Output is correct