oj.uz

Submission #941353

# Submission time Handle Problem Language Result Execution time Memory
941353 2024-03-08T15:32:05 Z phoenix0423 Alternating Current (BOI18_alternating) C++17
19 / 100
 69 ms 19964 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;
    }
    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:99:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i = 0; i < nw.size(); i++){
      |                    ~~^~~~~~~~~~~
alternating.cpp:117:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int i = 0; i < nw.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 2732 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 2732 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 2732 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12232 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 48 ms 14716 KB Output is correct
4 Correct 22 ms 11972 KB Output is correct
5 Correct 41 ms 19880 KB Output is correct
6 Correct 69 ms 19904 KB Output is correct
7 Correct 40 ms 18112 KB Output is correct
8 Correct 4 ms 12376 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 50 ms 19964 KB Output is correct
11 Correct 32 ms 17612 KB Output is correct
12 Correct 37 ms 14284 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 9308 KB Output is correct
15 Correct 38 ms 16720 KB Output is correct
16 Correct 43 ms 15952 KB Output is correct
17 Correct 56 ms 17904 KB Output is correct
18 Correct 44 ms 13816 KB Output is correct
19 Correct 7 ms 12060 KB Output is correct
20 Correct 40 ms 18636 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 2732 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Incorrect 1 ms 4700 KB 'impossible' claimed, but there is a solution
13 Halted 0 ms 0 KB -