Submission #305560

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
305560	2020-09-23 14:00:49	nickmet2004	Exercise Deadlines (CCO20_day1problem2)	C++11	25 / 25	158 ms	14200 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n , d[N];
int F[N];
vector<int> E[N];
void upd(int i , int v){
    for(; i <=n; i += i & -i) F[i]+=v;
}
int get(int i){
    int sum = 0;
    for(; i; i -= i & -i) sum += F[i]; return sum;
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> d[i] ,E[d[i]].emplace_back(i);
    sort(d+ 1 , d + n + 1); for(int i=1; i<= n; ++i) if(d[i] < i){cout << -1; return 0;}
    for(int i = 1; i <= n; ++i) upd(i , 1);
    priority_queue<int> pq;
    long long ans =0;
    for(int i = n; i; --i){
        for(int x : E[i]) pq.push(x);
        int a= pq.top(); pq.pop();
        upd(n - a + 1 ,-1);
        ans += get(n - a + 1);
    }cout << ans;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

Main.cpp: In function 'int get(int)':
Main.cpp:14:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   14 |     for(; i; i -= i & -i) sum += F[i]; return sum;
      |     ^~~
Main.cpp:14:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   14 |     for(; i; i -= i & -i) sum += F[i]; return sum;
      |                                        ^~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 8 / 8