oj.uz

Submission #1100771

# Submission time Handle Problem Language Result Execution time Memory
1100771 2024-10-14T16:09:27 Z lampooppp Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 3000 ms 16720 KB 
#include <bits/stdc++.h>
using namespace std;

const int N=2e5;
const int inf = 1e9+7;

struct segtree
{
    int val=0;
    int lazy=0;
    int mx,mn;
}st[4*N+1];

struct card
{
    int l, r;
    int s=0;
    bool operator < (const card & o) const
    {
        if(r==o.r) return l < o.l;
        return r < o.r;
    }
}a[N+1],tmp;
int s[N+1], id[N+1];

void Set(int x, int low, int hi, int i, int s, int k)
{
    if(low==hi)
    {
        st[x].mn=k;
        st[x].mx=k;
        st[x].val=s;
        return;
    }
    int mid = low+hi>>1;
    if(i<=mid) Set(x*2,low,mid,i,s,k);
    else Set(x*2+1,mid+1,hi,i,s,k);
    st[x].mx = max(st[x*2].mx, st[x*2+1].mx);
    st[x].mn = min(st[x*2].mn, st[x*2+1].mn);
}

//lazy=0 -> 0
//lazy=1 -> ^1
//lazy=2 ->|1
//lazy=3 -> &1

void operate(int& a, int b)
{
    if(b==1) {a^=1; return;}
    if(b==2) {a=1; return;}
    if(b==3) {a=0; return;}
}

void change(int& a, int b)
{
    if(a==0) {a=b; return;}
    if(b==2 || b==3) {a=b; return;}
    if(a==1 && b==1) {a=0; return;}
    if(a==2 && b==1) {a=3; return;}
    if(a==3 && b==1) {a=2; return;}
}


void push(int x)
{
    if(st[x].lazy==0) return;
    operate(st[x*2].val,st[x].lazy);
    operate(st[x*2+1].val,st[x].lazy);
    change(st[x*2].lazy,st[x].lazy);
    change(st[x*2+1].lazy,st[x].lazy);
    st[x].lazy=0;
}

void updateXOR(int x, int low, int hi, int i , int j)
{
    if(low > hi || low > j || hi<i) return;
    if(low>=i && hi<=j)
    {
        st[x].val^=1;
        if(st[x].lazy==0) {st[x].lazy=1; return;}
        if(st[x].lazy==1) {st[x].lazy=0; return;}
        if(st[x].lazy==2) {st[x].lazy=3; return;}
        if(st[x].lazy==3) {st[x].lazy=2; return;}
    }
    int mid = low+hi>>1;
    push(x);
    updateXOR(x*2,low,mid,i,j);
    updateXOR(x*2+1,mid+1,hi,i,j);
}

void updateOR(int x, int low, int hi, int i, int j, int k)
{
    if(low > hi || low > j || hi<i || st[x].mn>k) return;
    if(low>=i && hi<=j)
    {
        if(st[x].mx<=k)
        {
            st[x].val=1;
            st[x].lazy=2;
            return;
        }
    }
    int mid =low+hi>>1;
    push(x);
    updateOR(x*2,low,mid,i,j,k);
    updateOR(x*2+1,mid+1,hi,i,j,k);
}

int get(int x, int low, int hi, int i)
{
    if(low==hi) return st[x].val;
    int mid = low+hi>>1;
    push(x);
    if(i<=mid) return get(x*2,low,mid,i);
    return get(x*2+1,mid+1,hi,i);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i].l >> a[i].r;
        if(a[i].l > a[i].r)
        {
            swap(a[i].l,a[i].r);
            a[i].s=1;
        }
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
    {
        Set(1,1,n,i,a[i].s,a[i].l);
    }
    while(k--)
    {
        int x;
        cin >> x;
        tmp.l=inf;
        tmp.r=x;
        int p = upper_bound(a+1,a+n+1,tmp)-a-1;
        updateXOR(1,1,n,1,p);
        updateOR(1,1,n,p+1,n,x);
        //cout << p << " " << get(1,1,n,2) << '\n';
    }
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        int x = get(1,1,n,i);
        //cout << a[i].l << " " << a[i].r << " ";
        //cout << x << "\n";
        if(x==1) ans+=(long long)a[i].r;
        else ans+=(long long)a[i].l;
    }
    //cout << '\n';
    cout << ans;

}

Compilation message

fortune_telling2.cpp: In function 'void Set(int, int, int, int, int, int)':
fortune_telling2.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = low+hi>>1;
      |               ~~~^~~
fortune_telling2.cpp: In function 'void updateXOR(int, int, int, int, int)':
fortune_telling2.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = low+hi>>1;
      |               ~~~^~~
fortune_telling2.cpp: In function 'void updateOR(int, int, int, int, int, int)':
fortune_telling2.cpp:103:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |     int mid =low+hi>>1;
      |              ~~~^~~
fortune_telling2.cpp: In function 'int get(int, int, int, int)':
fortune_telling2.cpp:112:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |     int mid = low+hi>>1;
      |               ~~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 10 ms 16560 KB Output is correct
4 Correct 10 ms 16720 KB Output is correct
5 Correct 9 ms 16564 KB Output is correct
6 Correct 6 ms 16720 KB Output is correct
7 Correct 5 ms 16720 KB Output is correct
8 Correct 6 ms 16720 KB Output is correct
9 Correct 4 ms 16720 KB Output is correct
10 Correct 5 ms 16720 KB Output is correct
11 Correct 4 ms 16720 KB Output is correct
12 Correct 4 ms 16720 KB Output is correct
13 Correct 4 ms 16720 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 10 ms 16560 KB Output is correct
4 Correct 10 ms 16720 KB Output is correct
5 Correct 9 ms 16564 KB Output is correct
6 Correct 6 ms 16720 KB Output is correct
7 Correct 5 ms 16720 KB Output is correct
8 Correct 6 ms 16720 KB Output is correct
9 Correct 4 ms 16720 KB Output is correct
10 Correct 5 ms 16720 KB Output is correct
11 Correct 4 ms 16720 KB Output is correct
12 Correct 4 ms 16720 KB Output is correct
13 Correct 4 ms 16720 KB Output is correct
14 Correct 584 ms 16720 KB Output is correct
15 Correct 2249 ms 16704 KB Output is correct
16 Execution timed out 3072 ms 16720 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16720 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 10 ms 16560 KB Output is correct
4 Correct 10 ms 16720 KB Output is correct
5 Correct 9 ms 16564 KB Output is correct
6 Correct 6 ms 16720 KB Output is correct
7 Correct 5 ms 16720 KB Output is correct
8 Correct 6 ms 16720 KB Output is correct
9 Correct 4 ms 16720 KB Output is correct
10 Correct 5 ms 16720 KB Output is correct
11 Correct 4 ms 16720 KB Output is correct
12 Correct 4 ms 16720 KB Output is correct
13 Correct 4 ms 16720 KB Output is correct
14 Correct 584 ms 16720 KB Output is correct
15 Correct 2249 ms 16704 KB Output is correct
16 Execution timed out 3072 ms 16720 KB Time limit exceeded
17 Halted 0 ms 0 KB -