Submission #1798273

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;
// typedef pair<int,int> pii;
// tree <pii,null_type,greater<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;
// cin.tie(0);
// std::ios::sync_with_stdio(false);
typedef long long LL;
const int N = 400005;
const int M = 205;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
const int MOD = 1e9+7;
const double eps = 1e-8;
int n,m;
int dp[N];
int s[N],pre[N];
std::vector<int> G[N];
class SegmentTree {
  public:
    SegmentTree(int size, int value):
        m_size(size),
        m_data(size * 2, value) {}
 
    void update(int position, int value) {
        for (position += m_size; position; position /= 2)
            m_data[position] = min(m_data[position], value);
    }
 
    int query(int from, int to) {
        int answer = numeric_limits<int>::max();
        for (from += m_size, to += m_size; from < to; from /= 2, to /= 2) {
            if (from & 1)
                answer = min(answer, m_data[from++]);
            if (to & 1)
                answer = min(answer, m_data[--to]);
        }
        return answer;
    }
 
  private:
    int m_size;
    vector<int> m_data;
};
void ini()
{
    fill(pre,pre+n+1,0);
    fill(dp,dp+n+1,n);
    for (int i=0;i<=n;i++)    
        G[i].clear();
}
int main()
{
    while (~scanf("%d",&n))
    {
        ini();
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            pre[i] = pre[i-1]+(1-s[i]);
        }
        scanf("%d",&m);
        for (int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
        }
        int ans = 0;
        dp[0] = 0;
        SegmentTree S(n+1,n);
        for (int i=1;i<=n;i++)
        {
            dp[i] = min(dp[i],dp[i-1]+s[i]);
            S.update(i-1,dp[i-1]-pre[i-1]);
            for (int j=0;j<G[i].size();j++)
            {
                int l = i;
                int r = G[i][j];
                int tmp = S.query(l-1,r);
                dp[r] = min(dp[r],tmp+pre[r]);
                S.update(r,tmp);
            }
            // cout<<"bug "<<endl;
            // for (int i=1;i<=n;i++)
            //     cout<<dp[i]<<" ";
            // cout<<endl;
            // for (int i=1;i<=n;i++)
            //     cout<<S.query(i-1,i)<<" ";
            // cout<<endl;
        }
        ans = dp[n];
        printf("%d\n", ans);
    }
    return 0;
}
 
/*
 
3
1 0 1
1
1 3

3
1 0 1
2
1 1
3 3

3
1 0 1
2
1 1
2 3
 
5
0 1 0 1 0
1
1 5
 
9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7
 
15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13
 
10
0 0 0 1 0 0 1 1 1 0
7
1 4
2 5
1 3
6 7
9 9
1 5
7 9
 
*/

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:70:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&s[i]);
                              ^
./Main.cpp:73:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&m);
                       ^
./Main.cpp:77:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
                                ^

Judge Result