两种题解

没用结构体

因为看不懂结构体在这道题的用处

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
 	int n,t,x;
    cin>>n>>t>>x;
    vector<int>a(t,1);
    while(n--){
        int l,r;
        cin>>l>>r;
        for(int i=l-1;i<=r-1;i++)a[i]=0;
    }
    int ans=0;
    for(int i=0;i<t;i++){
        if(a[i]){
            int ct=0;
            for(int j=i;j<t;j++){
                if(!a[j])break;
                ct++;
                a[j]=0;
            }
            ans+=ct/x;
        }
    }
    cout<<ans;
    return 0;
}

时间复杂度O(n * t)我是不会用markdown文档的蒟蒻

第二种（赛时代码）

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
 	int n,t,x;
    cin>>n>>t>>x;
    vector<int>d(t+2);
    d[1]=1;
    d[t+1]--;
    while(n--){
     	int l,r;
        cin>>l>>r;
        d[l]--;
        d[r+1]++;
    }
    int current=0,ans=0,ct=0;
    for(int i=1;i<=t;i++){
     	current+=d[i];
        if(current>0){
         	ct++;
            if(ct>=x){
             	ans++;
                ct-=x;
            }
        }else ct=0;
    }
    cout<<ans;
    return 0;
}

时间复杂度O(n+t)
似乎是差分优化