Submission #377077

#	Time	Username	Problem	Language	Result	Execution time	Memory
377077		ansol4328	Sails (IOI07_sails)	C++14	100 / 100	80 ms	4828 KiB

sails

#include<bits/stdc++.h>
#define F first
#define S second

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
P m[100005];
int A[100005];
bool in[100005];
set<int> St;

int main()
{
    scanf("%d",&n);
    for(int i=1 ; i<=n ; i++) scanf("%d %d",&m[i].F,&m[i].S);
    sort(m+1,m+1+n); int H=m[n].F;
    St.insert(H+1); in[H+1]=true; A[H+1]=-1;
    for(int i=1 ; i<=n ; i++){
        int cur=H-m[i].F+1;
        if(m[i].F!=m[i-1].F){
            int tmp=*(St.begin());
            if(A[tmp]==0 && in[tmp]) St.erase(tmp), in[tmp]=false;
            St.insert(cur), in[cur]=true;
        }
        auto it=St.upper_bound(cur+m[i].S-1);
        int fn=*it; it--; int st=*it;
        if(fn!=cur+m[i].S){
            int x=(fn-1)-(cur+m[i].S-1-st);
            // x~fn-1, cur~st-1
            A[cur]++, A[st]--;
            A[x]++, A[fn]--;
            if(A[cur]==1 && !in[cur]) St.insert(cur), in[cur]=true;
            if(A[x]==1 && !in[x]) St.insert(x), in[x]=true;
            if(cur!=st && A[st]==0 && in[st]) St.erase(st), in[st]=false;
            if(A[fn]==0 && in[fn]) St.erase(fn), in[fn]=false;
        }
        else{
            //cur~fn-1
            A[cur]++; A[fn]--;
            if(A[cur]==1 && !in[cur]) St.insert(cur), in[cur]=true;
            if(A[fn]==0 && in[fn]) St.erase(fn), in[fn]=false;
        }
    }
    //calculating
    ll ans=0, v=0;
    for(int i=1 ; i<=H ; i++){
        v+=A[i]; ans+=v*(v-1)/2LL;
    }
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
sails.cpp:18:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     for(int i=1 ; i<=n ; i++) scanf("%d %d",&m[i].F,&m[i].S);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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