oj.uz

Submission #377077

# Submission time Handle Problem Language Result Execution time Memory
377077 2021-03-13T00:53:03 Z ansol4328 Sails (IOI07_sails) C++14
100 / 100
 80 ms 4828 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 748 KB Output is correct
2 Correct 17 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2412 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2028 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2540 KB Output is correct
2 Correct 49 ms 3180 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4828 KB Output is correct
2 Correct 36 ms 2156 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3564 KB Output is correct
2 Correct 80 ms 2284 KB Output is correct