oj.uz

Submission #941355

# Submission time Handle Problem Language Result Execution time Memory
941355 2024-03-08T15:34:26 Z phoenix0423 Alternating Current (BOI18_alternating) C++17
19 / 100
 72 ms 19596 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e18;
int n, m;
vector<int> adj[maxn];

struct seg{
    int l, r, id;
    seg(){}
    seg(int _l, int _r, int _id) : l(_l), r(_r), id(_id){
        if(r < l) r += n;
        else l += n, r += n;
    }
    bool operator < (const seg& other) const{
        if(l != other.l) return l < other.l;
        return r > other.r;
    }
};

class comp{
    public:
        bool operator ()(seg a, seg b){
            if(a.r != b.r) return a.r < b.r;
            else return a.l < b.l;
        }
};
struct segtree{
    int st[maxn * 4], tag[maxn * 4];
    void cast(int val, int v){
        st[v] += val, tag[v] += val;
    }

    void push(int v){
        if(tag[v]){
            cast(tag[v], v * 2);
            cast(tag[v], v * 2 + 1);
            tag[v] = 0;
        }
    }
    void upd(int l, int r, int val, int v, int L, int R){
        if(l > R || r < L) return;
        if(l <= L && r >= R){
            st[v] += val, tag[v] += val;
            return;
        }
        push(v);
        int m = (L + R) / 2;
        upd(l, r, val, v * 2, L, m);
        upd(l, r, val, v * 2 + 1, m + 1, R);
        st[v] = min(st[v * 2], st[v * 2 + 1]);
    }
    void upd(int l, int r, int val){ upd(l, r, val, 1, 0, n - 1);}
    int qry(int l, int r, int v, int L, int R){
        if(l > R || r < L) return INF;
        if(l <= L && r >= R) return st[v];
        push(v);
        int m = (L + R) / 2;
        return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
    }
    int qry(int l, int r){ return qry(l, r, 1, 0, n - 1);}
    void insert(int l, int r, int val){
        l %= n, r %= n;
        if(l <= r) upd(l, r, val);
        else upd(l, n - 1, val), upd(0, r, val);
    }
} st[2];

signed main(void){
    fastio;
    cin>>n>>m;
    vector<seg> e;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        e.pb(seg(a, b, i));
    }
    vector<int> par(m, -1);
    sort(e.begin(), e.end());
    int tr = -1, tid = -1;
    vector<seg> nw;
    for(int i = 0; i < m; i++){
        auto [l, r, id] = e[i];
        if(r <= tr) par[id] = tid, adj[tid].pb(i);
        else tr = r, tid = nw.size(), nw.pb(e[i]);
    }
    // for(int i = 0; i < m; i++) cout<<par[i]<<" ";
    // cout<<"\n";
    vector<int> ans(m);
    for(int i = 0; i < nw.size(); i++){
        st[i % 2].insert(nw[i].l, nw[i].r, 1);
        ans[nw[i].id] = i % 2;
        for(auto id : adj[i]){
            st[(i % 2 == 0)].insert(e[id].l, e[id].r, 1);
            ans[e[id].id] = (i % 2 == 0);
        }
    }
    if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
        for(auto x : ans) cout<<x;
        cout<<"\n";
        return 0;
    }
    if(nw.size() % 2 == 0){
        cout<<"impossible\n";
        return 0;
    }
    else{
        for(int i = 0; i < nw.size(); i++){
            st[i % 2].insert(nw[i].l, nw[i].r, -1);
            st[(i % 2 == 0)].insert(nw[i].l, nw[i].r, 1);
            ans[nw[i].id] ^= 1;
            for(auto id : adj[i]){
                st[(i % 2 == 0)].insert(e[id].l, e[id].r, -1);
                st[i % 2].insert(e[id].l, e[id].r, 1);
                ans[e[id].id] ^= 1;
            }
            if(st[0].qry(0, n - 1) >= 1 && st[1].qry(0, n - 1) >= 1){
                for(auto x : ans) cout<<x;
                cout<<"\n";
                return 0;
            }
        }
        cout<<"impossible\n";
    }

}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:100:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0; i < nw.size(); i++){
      |                    ~~^~~~~~~~~~~
alternating.cpp:118:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int i = 0; i < nw.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4784 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4912 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4908 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct
21 Correct 1 ms 2860 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
25 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4784 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4912 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4908 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct
21 Correct 1 ms 2860 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
25 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4784 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4912 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4908 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct
21 Correct 1 ms 2860 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
25 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12492 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 44 ms 14788 KB Output is correct
4 Correct 28 ms 11468 KB Output is correct
5 Correct 42 ms 18504 KB Output is correct
6 Correct 72 ms 19596 KB Output is correct
7 Correct 37 ms 17008 KB Output is correct
8 Correct 4 ms 12376 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 43 ms 18628 KB Output is correct
11 Correct 32 ms 16588 KB Output is correct
12 Correct 36 ms 13504 KB Output is correct
13 Correct 1 ms 7256 KB Output is correct
14 Correct 1 ms 9308 KB Output is correct
15 Correct 39 ms 15268 KB Output is correct
16 Correct 43 ms 15440 KB Output is correct
17 Correct 56 ms 16440 KB Output is correct
18 Correct 46 ms 12228 KB Output is correct
19 Correct 9 ms 12056 KB Output is correct
20 Correct 40 ms 17528 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4784 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 1 ms 4912 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4908 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct
21 Correct 1 ms 2860 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
25 Halted 0 ms 0 KB -