oj.uz

Submission #971206

# Submission time Handle Problem Language Result Execution time Memory
971206 2024-04-28T06:39:33 Z yeediot Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 352 ms 46564 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
const int mxn=2e5+5;
int n,q;
int a[mxn],b[mxn];
vector<int>temp;
struct segtree{
    int seg[12*mxn];
    void build(int l,int r,int id){
        seg[id]=0;
        if(l==r){
            return;
        }
        int mm=l+r>>1;
        build(l,mm,id*2);
        build(mm+1,r,id*2+1);
    }
    void modify(int l,int r,int id,int p,int v){
        if(l==r){
            seg[id]=max(seg[id],v);
            return;
        }
        int mm=l+r>>1;
        if(p<=mm){
            modify(l,mm,id*2,p,v);
        }
        else{
            modify(mm+1,r,id*2+1,p,v);
        }
        seg[id]=max(seg[id*2],seg[id*2+1]);
    }
    int query(int l,int r,int id,int ql,int qr){
        if(qr<l or r<ql){
            return 0;
        }
        if(ql<=l and r<=qr){
            return seg[id];
        }
        int mm=l+r>>1;
        return max(query(l,mm,id*2,ql,qr),query(mm+1,r,id*2+1,ql,qr));
    }
}tr;
bool cmp(int i,int j){
    return max(a[i],b[i])>max(a[j],b[j]);
}
int get(int x){
    return lower_bound(all(temp),x)-temp.begin()+1;
}
struct BIT{
    int bit[mxn];
    void init(){
        for(int i=0;i<mxn;i++){
            bit[i]=0;
        }
    }
    void modify(int p,int v){
        for(;p<mxn;p+=p&-p){
            bit[p]+=v;
        }
    }
    int query(int p){
        if(p<0)return 0;
        int res=0;
        for(;p;p-=p&-p){
            res+=bit[p];
        }
        return res;
    }
}browntoad;
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        temp.pb(min(a[i],b[i]));
        temp.pb(max(a[i],b[i])-1);
    }
    vector<int>ord(n);
    for(int i=0;i<n;i++){
        ord[i]=i+1;
    }
    sort(all(ord),cmp);
    vector<pair<int,int>>op;
    for(int i=0;i<q;i++){
        int x;
        cin>>x;
        op.pb({x,i});
        temp.pb(x);
    }
    sort(all(temp));
    temp.resize(unique(all(temp))-temp.begin());
    tr.build(1,2*n+q,1);
    for(int i=0;i<q;i++){
        tr.modify(1,2*n+q,1,get(op[i].F),i+1);
    }
    sort(all(op),greater<pii>());
    int ans=0;
    browntoad.init();
    int p=0;
    for(int i=0;i<n;i++){
        int id=ord[i];
        debug(id);
        while(p<q and op[p].F>=max(a[id],b[id])){
            browntoad.modify(op[p].S+1,1);
            p++;
        }
        int pos=tr.query(1,2*n+q,1,get(min(a[id],b[id])),get(max(a[id],b[id])-1));
        int parity=(browntoad.query(q)-browntoad.query(pos))%2;
        if(pos!=0){
            if(a[id]>b[id]){
                if(parity%2==1){
                    ans+=b[id];
                }
                else{
                    ans+=a[id];
                }
            }
            else{
                if(parity%2==1){
                    ans+=a[id];
                }
                else{
                    ans+=b[id];
                }
            }
        }
        else{
            if(parity%2==1){
                ans+=b[id];
            }
            else{
                ans+=a[id];
            }
        }
    }
    cout<<ans<<'\n';
}

 /*
 input:
 
 */

Compilation message

fortune_telling2.cpp: In member function 'void segtree::build(long long int, long long int, long long int)':
fortune_telling2.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mm=l+r>>1;
      |                ~^~
fortune_telling2.cpp: In member function 'void segtree::modify(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:74:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mm=l+r>>1;
      |                ~^~
fortune_telling2.cpp: In member function 'long long int segtree::query(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:90:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int mm=l+r>>1;
      |                ~^~
fortune_telling2.cpp: In function 'void setIO(std::string)':
fortune_telling2.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6656 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 13 ms 7516 KB Output is correct
15 Correct 26 ms 10332 KB Output is correct
16 Correct 40 ms 11484 KB Output is correct
17 Correct 53 ms 11976 KB Output is correct
18 Correct 53 ms 11856 KB Output is correct
19 Correct 51 ms 12008 KB Output is correct
20 Correct 51 ms 11868 KB Output is correct
21 Correct 51 ms 11852 KB Output is correct
22 Correct 39 ms 11372 KB Output is correct
23 Correct 39 ms 11352 KB Output is correct
24 Correct 38 ms 11344 KB Output is correct
25 Correct 40 ms 11412 KB Output is correct
26 Correct 39 ms 11612 KB Output is correct
27 Correct 43 ms 11868 KB Output is correct
28 Correct 44 ms 12020 KB Output is correct
29 Correct 49 ms 12100 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 3 ms 6656 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 13 ms 7516 KB Output is correct
15 Correct 26 ms 10332 KB Output is correct
16 Correct 40 ms 11484 KB Output is correct
17 Correct 53 ms 11976 KB Output is correct
18 Correct 53 ms 11856 KB Output is correct
19 Correct 51 ms 12008 KB Output is correct
20 Correct 51 ms 11868 KB Output is correct
21 Correct 51 ms 11852 KB Output is correct
22 Correct 39 ms 11372 KB Output is correct
23 Correct 39 ms 11352 KB Output is correct
24 Correct 38 ms 11344 KB Output is correct
25 Correct 40 ms 11412 KB Output is correct
26 Correct 39 ms 11612 KB Output is correct
27 Correct 43 ms 11868 KB Output is correct
28 Correct 44 ms 12020 KB Output is correct
29 Correct 49 ms 12100 KB Output is correct
30 Correct 112 ms 17968 KB Output is correct
31 Correct 166 ms 26424 KB Output is correct
32 Correct 210 ms 26936 KB Output is correct
33 Correct 351 ms 43704 KB Output is correct
34 Correct 98 ms 17560 KB Output is correct
35 Correct 352 ms 44496 KB Output is correct
36 Correct 347 ms 43680 KB Output is correct
37 Correct 351 ms 45064 KB Output is correct
38 Correct 325 ms 44956 KB Output is correct
39 Correct 319 ms 45628 KB Output is correct
40 Correct 308 ms 43704 KB Output is correct
41 Correct 318 ms 43804 KB Output is correct
42 Correct 300 ms 44176 KB Output is correct
43 Correct 216 ms 43408 KB Output is correct
44 Correct 216 ms 43592 KB Output is correct
45 Correct 212 ms 42676 KB Output is correct
46 Correct 233 ms 42684 KB Output is correct
47 Correct 214 ms 43212 KB Output is correct
48 Correct 246 ms 44476 KB Output is correct
49 Correct 236 ms 46564 KB Output is correct